221004 문제 풀이 기록
P4 | 1209 - 단조 수열 만들기
풀이 시간: 1시간
시도 횟수: 7회
체감 난이도: P3
풀이 쓸 의향: 中
풀이
모든 B의 원소는 A의 원소만으로 이루어져도 최적값을 찾을 수 있다는 사실을 증명한 뒤, N^2 DP로 풀기
여담: 범위가 Long Long 범위인데 dp값 초기화를 INT_MAX로 조져버리는 바람에 20분이나 낭비했다... 요즘 자꾸 왜이러지 진짜;
'PS > 풀이 기록장' 카테고리의 다른 글
| 221008 문제 풀이 기록 (0) | 2022.10.08 |
|---|---|
| 221006 문제 풀이 기록 (0) | 2022.10.06 |
| 221003 문제 풀이 기록 (0) | 2022.10.04 |
| 221002 문제 풀이 기록 (0) | 2022.10.02 |
| 221001 문제 풀이 기록 (0) | 2022.10.02 |
221003 문제 풀이 기록
P4 | 14459 - 소가 길을 건너간 이유 11
풀이 시간: X
시도 횟수: 2회
체감 난이도: X
풀이 쓸 의향: 下
풀이
9*N LIS 돌리는데, pair<int, int>에서 l은 오름차순, r을 내림차순으로 정렬한 뒤 lis를 돌리자.
여담: 답을 슬쩍 보고 풀어서... LIS를 이렇게 활용할 수도 있구나 배워가는 시간이었다.
'PS > 풀이 기록장' 카테고리의 다른 글
| 221006 문제 풀이 기록 (0) | 2022.10.06 |
|---|---|
| 221004 문제 풀이 기록 (0) | 2022.10.04 |
| 221002 문제 풀이 기록 (0) | 2022.10.02 |
| 221001 문제 풀이 기록 (0) | 2022.10.02 |
| 220925 문제 풀이 기록 (0) | 2022.09.26 |
221002 문제 풀이 기록
P4 | 14458 - 소가 길을 건너간 이유 10
풀이 시간: 1시간
시도 횟수: 6회
체감 난이도: P3
풀이 쓸 의향: 下
풀이
segtree로 일단 초기 쌍 세어준 다음에, 왼쪽 올리기 & 오른쪽 올리기 하면 왼쪽 & 오른쪽 내림차순 정렬한 후에 순서대로 올려주면서 최솟값 찾기
여담: 잘 풀어놓고 오른쪽만 올려도 되겠지 하는 안일한 생각에 30분을 추가로 날려버린 나... 어쩌면 멍청이일지도??
'PS > 풀이 기록장' 카테고리의 다른 글
| 221004 문제 풀이 기록 (0) | 2022.10.04 |
|---|---|
| 221003 문제 풀이 기록 (0) | 2022.10.04 |
| 221001 문제 풀이 기록 (0) | 2022.10.02 |
| 220925 문제 풀이 기록 (0) | 2022.09.26 |
| 220924 문제 풀이 기록 (0) | 2022.09.25 |
221001 문제 풀이 기록
P4 | 14463 - 소가 길을 건너간 이유 9
풀이 시간: 50분
시도 횟수: 3회
체감 난이도: P4
풀이 쓸 의향: 下
풀이
시작점, 끝점을 시작점 기준으로 정렬해두고 세그트리로 개수 세기
여담: 문제 처음에 잘못 읽고 두번 박았음... 겹치는 경로를 가지는 소의 수를 세는건줄 알았는데 겹치는 쌍의 수를 세는거였단걸 50분 지나고 나서 깨달아버림 ;(
'PS > 풀이 기록장' 카테고리의 다른 글
| 221003 문제 풀이 기록 (0) | 2022.10.04 |
|---|---|
| 221002 문제 풀이 기록 (0) | 2022.10.02 |
| 220925 문제 풀이 기록 (0) | 2022.09.26 |
| 220924 문제 풀이 기록 (0) | 2022.09.25 |
| 220923 문제 풀이 기록 (0) | 2022.09.24 |
220925 문제 풀이 기록
P3 | 5896 - 효율적으로 소 사기
풀이 시간: 약 1시간 30분 + a
시도 횟수: 4회
체감 난이도: P3
풀이 쓸 의향: 下
풀이
쿠폰 오름차순 / 일반가 오름차순 각각의 pq 두개 만들어두고, 쿠폰 오름차순부터 차례대로 보면서 최소값으로만 고르기
여담: pq 심화 문제였는데, 너무 헤맸다... 너무 그리디를 다른 방식으로만 생각한 것 같다.
P3 | 5910 - Mountain Climbing
풀이 시간: 1시간 20분
시도 횟수: 3회
체감 난이도: P3
풀이 쓸 의향: 下
풀이
down>=up과 down<up 두 가지로 나눠보면 down>=up인것 우선으로, down>=up이면 up 오름차순 / down<up이면 down 내림차순 정렬하여 둔 것이 최적이라는 사실을 증명한 뒤에 구현하기
여담: 대체 이걸 어떻게 생각해야 할지 감도 안와서 문제 풀다 잠깐 쉬고 와서 다시 풀었다. 오늘 푼 그리디 두 문제 모두 내가 지금까지 봐왔던 그리디랑은 조금 다른 형태의 그리디였는데, 한 관찰에서 20분 이상 생각하지 말고 20분 넘게 관찰하다가 해당 방향으로 관찰이 힘들면 다른 방식으로 관찰해야겠다. 이 문제를 풀 때는 반드시 down이 연속적으로 되면 맨 앞의 up + sum(down)일 것인데, 이때 up을 어떻게 구할지 내지는 down이 어떻게 연속이 될 수 있을지를 보고 있었는데, 결과적으로는 아예 쓸데없는 관찰이었다.
'PS > 풀이 기록장' 카테고리의 다른 글
| 221002 문제 풀이 기록 (0) | 2022.10.02 |
|---|---|
| 221001 문제 풀이 기록 (0) | 2022.10.02 |
| 220924 문제 풀이 기록 (0) | 2022.09.25 |
| 220923 문제 풀이 기록 (0) | 2022.09.24 |
| 220922 문제 풀이 기록 (0) | 2022.09.23 |