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 |