분류 전체보기
-
221012 문제 풀이 기록2022.10.12
-
221011 문제 풀이 기록2022.10.11
-
221010 문제 풀이 기록2022.10.10
-
221008 문제 풀이 기록2022.10.08
-
221006 문제 풀이 기록2022.10.06
-
221004 문제 풀이 기록2022.10.04
-
221003 문제 풀이 기록2022.10.04
-
221002 문제 풀이 기록2022.10.02
-
221001 문제 풀이 기록2022.10.02
-
220925 문제 풀이 기록2022.09.26
221012 문제 풀이 기록
P3 | 6000 - 동전 게임
풀이 시간: 40분 + 30분;;;;
시도 횟수: 분노의 꼬라박기 7회
체감 난이도: P3
풀이 쓸 의향: 下
풀이
dp[i][j] = i번째 턴에 최대 j개까지의 동전을 가져갈 수 있을 때의 최댓값, cnt[i][j] = 그때 가져가는 동전 갯수 를 저장하고 돌리기.
여담: "오늘 좀 잘풀었는데???" 생각하고 첫 제출하니까 MLE떠서 여러번 박았다가 결국 cnt 배열을 short로 선언해서 AC맞았다...
그리고 다른 사람 풀이 보니까 int로 선언해서 31MB 풀이로 풀린게 있던데... :(( 탑다운 DP 못하면 억까 당해야지 뭐...
'PS > 풀이 기록장' 카테고리의 다른 글
| 221021 문제 풀이 기록 (0) | 2022.10.22 |
|---|---|
| 221014 ~ 221017 문제 풀이 기록 (0) | 2022.10.17 |
| 221011 문제 풀이 기록 (0) | 2022.10.11 |
| 221008 문제 풀이 기록 (0) | 2022.10.08 |
| 221006 문제 풀이 기록 (0) | 2022.10.06 |
221011 문제 풀이 기록
P4 | 11993 - Circular Barn (Gold)
풀이 시간: 1시간
시도 횟수: 2회
체감 난이도: P4
풀이 쓸 의향: 中
풀이
가장 왼쪽에 근접한 원소를 고르는 것이 최적이다.
여담: 투포인터 구현 실수해서 -1.
다른 사람 코드 보고 알았는데, queue로 하면 훨씬 쉬움... 아니 어떻게 이 생각을 못하지;;;;;;;
'PS > 풀이 기록장' 카테고리의 다른 글
| 221014 ~ 221017 문제 풀이 기록 (0) | 2022.10.17 |
|---|---|
| 221012 문제 풀이 기록 (0) | 2022.10.12 |
| 221008 문제 풀이 기록 (0) | 2022.10.08 |
| 221006 문제 풀이 기록 (0) | 2022.10.06 |
| 221004 문제 풀이 기록 (0) | 2022.10.04 |
221010 문제 풀이 기록
P3 | 6101 - 식당
풀이 시간: 2시간 + a
시도 횟수: 4회
체감 난이도: P3
풀이 쓸 의향: 中
풀이
N*sqrt(N)으로 DP 돌리기 : queue를 활용해서 종류가 x개이면서 범위가 가장 큰 구간 찾은 뒤에, 해당 값을 이용하여 DP 테이블 채우기
여담: 답지의 위 몇줄을 보고 풀었는데... 아니 어떻게 이런 아름다운 생각을 할 수 있는지.. 참........ :(
P4 | 11375 - 열혈강호
풀이 시간: 30분
시도 횟수: 1회
체감 난이도: P5
풀이 쓸 의향: 下
풀이
이분 매칭 입문 문제
여담: 이분 매칭에 대해 배웠다. 근데 이분 매칭 입문 문제가 P4나 될정도로 이분 매칭 개념 자체가 어렵진 않아 보이는데...
P4 | 11376 - 열혈강호 2
풀이 시간: 위 문제 + 10분
시도 횟수: 4회
체감 난이도: P4
풀이 쓸 의향: 下
풀이
위 문제에서 dfs 두번씩 돌리기
여담: 열혈강호 문제와 별 다를 바가 없지만, 단순히 dfs를 두 번씩 돌려주는것만으로 충분히 가능하다고 생각해내기
P3 | 11377 - 열혈강호 3
풀이 시간: 위 문제 + 3분
시도 횟수: 1회
체감 난이도: P4
풀이 쓸 의향: 下
풀이
위 문제에서 dfs 2번 돌리는 횟수를 k번까지만 하기
여담: 열혈강호 2와 사실상 동일한 문젠데 왜 난이도가 다른지 모르겠다
P3 | 11378 - 열혈강호 4
풀이 시간: 위 문제 + 2분
시도 횟수: 1회
체감 난이도: P4
풀이 쓸 의향: 下
풀이
위 문제에서 dfs 최대 K번 돌리기 (가능하면 계속 돌리고, 아니면 다음으로 넘어가기)
여담: 얘도 마찬가지...
P3 | 1017 - 소수 쌍
풀이 시간: 37분
시도 횟수: 2회
체감 난이도: P3
풀이 쓸 의향: 下
풀이
이분 매칭 응용 문제... 짝수 + 홀수만 소수가 될 수 있다는 점을 파악하여 좌/우 구분 후 이분 매칭 돌리기
여담: 벡터 크기 안맞춰줬다가 한번 틀렸다... :( 너무해....
그래도 이분 매칭 연습 용으로 좋았던 것 같다.
이분 매칭 문제 날먹으로 P1 달성!!!
P3도 제대로 못푸는 P1이 되어버린 나... 어쩌면 큰일났을지도??
221008 문제 풀이 기록
P4 | 16764 - Cowpatibility
풀이 시간: 1시간
시도 횟수: 4회
체감 난이도: P4
풀이 쓸 의향: 下
풀이
map<vector<int>, int>로 관리하면서 포함/배제의 원리 사용하여 bitmasking 하기
여담: 이런 것도 되는지는 이번에 처음 알았다... 뭐지 이 문제???
'PS > 풀이 기록장' 카테고리의 다른 글
| 221012 문제 풀이 기록 (0) | 2022.10.12 |
|---|---|
| 221011 문제 풀이 기록 (0) | 2022.10.11 |
| 221006 문제 풀이 기록 (0) | 2022.10.06 |
| 221004 문제 풀이 기록 (0) | 2022.10.04 |
| 221003 문제 풀이 기록 (0) | 2022.10.04 |
221006 문제 풀이 기록
P4 | 6142 - Gourmet Grazers
풀이 시간: 20분
시도 횟수: 1회
체감 난이도: P4 하위권
풀이 쓸 의향: 下
풀이
각각의 pair 배열을 green 내림차순 정렬 후, 마트 재고 중 해당 greenness보다 큰 grenness를 가진 것들 중 비용이 최소 비용 이상인 가장 작은 물품 구매하기. multiset lower_bound로 쉽게 해결 가능.
여담: 풀이가 빠르게 떠올라서 쉽게 풀었다.
P4 | 14449 - Balanced Photo
풀이 시간: 15분
시도 횟수: 1회
체감 난이도: P4
풀이 쓸 의향: 下
풀이
값 압축을 통해 h_i를 [1, N] 사이 범위로 바꿔준 뒤, 순서대로 [해당 값, N] 사이의 원소의 개수를 segtree로 세어주며 l_i, r_i 구하기
여담: 값 압축 안하고 키 내림차순 정렬 후 세그트리를 써도 풀린다. 세그트리에 순서를 넣는다는 아이디어보다 압축된 값을 넣는다는 아이디어가 더 빠르게 떠올라서 그냥 값 압축 세그트리를 쓰긴 했지만...
뭔가 두 문제 다 너무 빨리 풀어서 날먹한 기분... 뭐지?
'PS > 풀이 기록장' 카테고리의 다른 글
| 221011 문제 풀이 기록 (0) | 2022.10.11 |
|---|---|
| 221008 문제 풀이 기록 (0) | 2022.10.08 |
| 221004 문제 풀이 기록 (0) | 2022.10.04 |
| 221003 문제 풀이 기록 (0) | 2022.10.04 |
| 221002 문제 풀이 기록 (0) | 2022.10.02 |
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 |