2달 간 푼 문제를 모두 작성하진 못하고 기억에 남거나 얻어가는게 있던 문제 위주로 작성하였습니다.
[백준 - 20667] 크롬
문제: https://www.acmicpc.net/problem/20667
제약 조건이 2개인 냅색문제였다.
단순히 냅색으로 풀려면 1,000 * 100,000 만큼의 공간이 필요하므로 불가능 하다.
굉장히 오래 고민했지만 결과적으로 중요도가 1~5 범위 라는 것이 키포인트 였다.
범위가 1000 까지인 CPU 사용량과 최대 500까지 나오는 중요도로 DP배열을 만들고 배열엔 가장 낮은 메모리를 기록하면 된다.
최소로 줄여야하는 CPU 사용량을 만족한 DP배열을 순회하면서 해당 값(메모리)가 조건을 만족한다면 index로 사용한 중요도를 기록한다.
기본적으로 떠오르는 접근방법은 "제약 조건을 모두 만족하는 경우에서 가장 낮은 중요도를 찾는다" 이기 때문에 간단하면서도 허를 찌르는 문제였다.
[백준 - 20668] 카트라이더
문제: https://www.acmicpc.net/problem/20668
같은 장소에 있더라도 속도가 다르면 도착 시간과 도착 속도가 달라지는데 어떻게 처리할까?
-> 속도가 다르면 같은 장소가 아닌것 처럼 취급하자.
마치 10층짜리 건물이 있어 해당 건물은 다른 10층짜리 건물과 연결 되어 있는데, 층마다 연결 다리가 다른 것이라 생각이 들었다.
그러나 이러한 아이디어 만으로는 AC 받기에 충분치 않았다.
소수점 9자리까지 정확도를 요구하는데, 정점이 10000개에 거리도 최대 10만 이므로 시간이 대충 10000 * 10만 까지도 걸릴 수 있다.
double은 정수부가 커지면 소수부의 정확도가 더 떨어진다.
그래서 우선순위 큐를 포함해 모든 거리 정보를 정수부와 소수부로 나눠서 저장했다.
마지막에 따로따로 잘 출력했더니 AC를 받았다.
- 같은 장소에 있더라도 조건이 다르면 다른 장소인 것 처럼 취급하기
- 정수부가 클 때 소수부의 정확도 유지시키는 방법
얻어가는게 2가지나 있던 좋은 문제였다.
[백준 - 15769] PuyoPuyo
문제: https://www.acmicpc.net/problem/15769
원하는 뿌요: 1, 관계없는 뿌요: 2 로 표현하겠다.
처음부터 횟수에 구애받지 않고 확실히 모양 만들기가 가능한 방법을 생각해봤다.
다음과 같은 방법으로 왼쪽에서부터 오른쪽줄을 처리한다.
세로로 계속 뿌요를 쌓는다. 짝수면 처리 끝.
홀수 개라서 위쪽에 1개밖에 안남은 경우가 생기면
2
1
모양으로 쌓고, 위에 세로로 된 2 2를 2개 더 얹어서 2를 없앤다
이 방법에는 2가지 문제점이 있다.
1. 필요없는 2를 없애기 위해 2를 연속으로 쌓아 터뜨리다가 옆에 뿌요와 연결되어 함께 터질 가능성이있다.
2. 높이가 정확히 H-1에서 끝나는 곳은 2 2를 두번 쌓는게 불가능 하다.
처리 과정을 다음과 같이 수정하면 두 문제점을 모두 해결 할 수 있다.
- 높이가 홀수인 블록을 파악하고, 제일 밑에 해당하는 뿌요 1개를 남도록 한다. 1 2/2 2/2 2(세로) 를 쌓는 식이다.
- 이제 남은 높이가 전부 짝수이므로 세로로 쌓는다.
20x20에 전부 높이가 H-1인 최악의 경우도 240번만에 풀 수 있다.
횟수제한이 220이나 230이였으면 좀더 어려운 문제가 됐을 것 같다.
사실 난 220번만에 가능하게 짰다...
[백준 - 1738] 골목길
문제: https://www.acmicpc.net/problem/1738
가중치의 부호에 제약이 없어 음의 사이클이 있는지도 파악해야 하는 문제이다.
이론으로 배워보기만하고 한번도 써먹어 본적 없는 벨만-포드 알고리즘을 복습하는 기회가 되었다.
단순히 음의 사이클을 파악하는 것 만으로는 문제를 풀기에 충분치 않았는데, 해당 사이클에서 목표지점까지 도달이 불가능하면 상관이 없기 때문이였다.
음의 사이클을 모두 파악하고, 도착지점에서 역방향 간선을 타고 음의 사이클에 도달 가능하면 그제서야 불가능한 경우라고 판단을 내려야 했다.
벨만-포드 알고리즘의 복습뿐만 아니라, 도착지점에서 음의 사이클에 도달 가능한지 파악 해야한다는 점을 알게해준 문제였다.
[백준 - 2533] 사회망 서비스(SNS)
문제: https://www.acmicpc.net/problem/2533
노드의 깊이를 기록하고 리프노드를 만나면 우선순위 큐에 넣어 깊이가 깊은 리프노드 순서대로 처리했다.
- 리프노드가 얼리어답터 인 것보다 리프노드의 부모가 얼리어답터인 것이 항상 이득이다. 따라서 리프노드의 부모를 얼리어답터로 한다.
- 얼리어답터의 부모는 리프노드로 취급하여 우선순위 큐에 넣는다.
