코드잼 1A, 1B를 모두 떨어지고 어느새 마지막 기회인 1C밖에 안남았다...
이번주 토요일에 코드잼을 보기전에 복습을 해야겠다.
[백준 - 8983] 사냥꾼
문제: https://www.acmicpc.net/problem/8983
동물을 입력 받을 때 마다 x좌표가 가장 가까운 사냥꾼이 사냥할 수 있는지 파악하면 되는 문제.
정렬 + 이진 탐색으로 O(NlogN)에 가능하다.
[백준 - 2271] 암호화 알고리즘
문제: https://www.acmicpc.net/problem/2271
의외로 O(N^2)으로도 풀리는 문제다.
q와 s를 고르는데 O(N^2)을 쓰고 O(1)만에 p랑 r을 구하면 된다.
q<s 라면 기본 전략은 r은 범위내에서 가장 큰 수를 찾고, p를 찾는 것이다.
나는 p를 찾을 때 범위내에서 s 보다 큰 수중에 가장 작은 수를 찾았다.
O(N^2)으로 미리 전처리를 해두어서 바로 구할 수 있었지만 메모리 초과가 나서
short로 바꾸니 아슬아슬하게 통과했다.
정석 풀이는 희소배열을 이용해서 최솟값을 구하는 풀이이다.
수의 범위가 1~10000이므로, 수의 크기를 인덱스로 하고, 위치를 값을 같은 배열을 이용해 어찌저찌하면 p를 구할 수 있더라.
여담으로 그냥 set과 lower_bound로 O(N^2logN)인 코드가 나보다 훨씬 빨랐다;
[백준 - 1655] 가운데를 말해요
문제: https://www.acmicpc.net/problem/1655
시간제한이 0.1초라서 엄청 쫄았는데 다행이 O(NlogN)으로 잘 풀리는 문제였다.
정석 풀이는 우선순위 큐인것 같은데 나는 set과 링크드 리스트로 풀었다.
링크드 리스트의 주소를 숫자 크기에 따라 0~20000의 배열에 담아 두었다.
가운데를 가르키는 포인터를 잡고 들어올 때마다 링크드 리스트에 추가하고 가운데 포인터를 이동시켰다.
포인터를 이동시킬 떄 set을 통해 바로 옆 숫자가 뭔지 파악했다.
[백준 - 14752] Map Labeling
문제 : https://www.acmicpc.net/problem/14752
dp[i][j]: i번 째를 보는 중 이고 j개가 직선일 때 최소 위치.
dp[i-1][j-1]과 dp[i-1][j]에서 잘 뽑아오고 처리하면 된다.
코드잼 Round 1C 2021 에서 1110등을 해서 아마 Round 2에 진출 할 것 같다!
