0912~0913

16001. 보물상자 열기

문제 링크: https://www.acmicpc.net/problem/16001

카카오 대회 본선 당일에 못 풀었던 문제를 풀었다. 풀이는 비교적 빨리 떠올랐고 결국 그 풀이가 맞았는데, 구현 과정에서 정말 많은 오류를 범했다.

내 풀이는,

1. 맨 왼쪽 위치에서부터 시작해서 오른쪽으로 가면서 팰린드롬 만드는 최소 비용을 찾는다.

2. 1번 값을 이용해서 sliding window 같은 방식으로 1,2,3,...번째에서 시작해서 오른쪽으로 가면서 팰린드롬 만드는 최소 비용을 모두 구한다.

3. 이렇게 구한 값을 이용해서, 각 시작 위치별로 최소 비용을 찾는다. 이 때 항상 나보다 오른쪽으로 가거나, 왼쪽 끝 지점까지 갔다가 오른쪽으로 가는 비용을 구한다. 이 경우, 2에서 구해둔 배열을 활용하면 한 칸 움직일 때마다 왼쪽 애들은 값이 전부 c씩 늘어나고, 오른쪽 애들은 전부 c씩 감소하기 때문에 O(N)에 구할 수 있다.

4. 오른쪽 -> 왼쪽으로 이동하는 경우도 고려하기 위해 전체를 뒤집어서 이 경우의 답도 구하고, 둘 중 더 작은 것을 고른다.

였는데, 놀랍게도 1,2,3의 모든 과정에 구현 실수가 있었고 이걸 다 고치는데 시간이 정말 오래 걸렸다. 반례 찾기도 힘들어서 O(n^4) 브루트 포스 알고리즘과 랜덤 케이스 생성기를 만들어서 폴리곤에서 반례 한참 찾아가며 고쳤다.

특히 1번 과정에서 실수가 많았는데, 역시 좀 더 확실하게 풀이를 구체화하지 않고 구현에 들어가는 나쁜 습관 때문에 시간을 정말 많이 낭비한 것 같다.

16128. 스눕시티

문제 링크: https://www.acmicpc.net/problem/16128

좋은 문제라는 평이 자자하던 스눕시티 문제를 풀었다. 빈칸을 옮겨서 도달하면 된다는 아이디어는 상당히 빨리 떠올렸는데, 나누는 위치를 잘못 생각해서, 큰 -> 작은으로 가야하는데 작은 -> 큰으로 볼 수 있을 거라고 생각하고 풀다가 몇 번 틀렸다. 다시 생각해보니 큰거에서 작은걸로 이동해야 제대로 된 사각형을 보면서 움직일 수 있어 보였고, 그래서 그렇게 고쳤는데 고치고 보니 시간복잡도가 O(2^n)이 된다는 것을 깨달았다. 여기서 O(n)으로 줄이기 위한 코너 케이스 처리가 상당히 좋은 문제였다.

하지만 잘못된 코딩 실수로 long long 처리를 잘못해서 한 시간동안 맞왜틀을 하고... 그것 때문에 풀이의 재미가 반감돼서 아쉽다 ㅠ 삽질 끝에 에휴 겨우 맞았네 라는 느낌만 남아버려서...