발자취

문제 설명을 잘 읽어보자. https://www.acmicpc.net/problem/14719 14719번: 빗물 첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500) 두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치 www.acmicpc.net 빗물이 고이는 특성은 다음과 같다. 1. 좌측 끝과 우측 끝이 벽으로 막혀 있어야 한다. 2. 빗물이 찼을 때 양쪽 끝이 같다. 3. 중간에 구멍이 생길 일은 전혀 없다. (주어진 조건이 밑에서부터 위로 몇 칸 있는지 확인하므로) 이러한 특징을 기반으로 다음과 같은 풀이 알고리즘을 생각해 보았다. 1. 수면의 높이가 1~N 일때까지 탐색한다. 2. 물이..

문제 설명을 보고 오자. https://www.acmicpc.net/problem/2661 2661번: 좋은수열 첫 번째 줄에 1, 2, 3으로만 이루어져 있는 길이가 N인 좋은 수열들 중에서 가장 작은 수를 나타내는 수열만 출력한다. 수열을 이루는 1, 2, 3들 사이에는 빈칸을 두지 않는다. www.acmicpc.net 이 문제는 백트래킹을 이용한 탐색 문제이다. 조건을 생각하는 구성이 복잡하지만, 역할을 잘 나누면 풀이가 한결 편해질 것이다. 인접한 두 개의 부분 수열이 동일한 것이 있으면, 해당 수열은 나쁜 수열로 다음 경우의 수로 넘어가야 한다. 그렇게 하기 위해서는 한 자리에 1~3이 들어가며, 조건에 맞으면 다음 과정을 탐색할 수 있는 백트래킹 기법으로 풀이하면 될 것이다. 탐색하는 함수를 ..