2020/05

이번에 풀어볼 문제는 DP문제인 동물원입니다. 1309번: 동물원 첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다. www.acmicpc.net 이문제는 오르막수와 비슷한 문제 양상을 띄고 있어서, 비슷한 문제 풀이를 이용했습니다. 이차원배열을 통해서 총 3가지의 경우를 나타냈는데 각각의 의미는 이렇습니다 Dp[n][0] -> 두 개의 방 중에 사자를 아예 넣지 않은 경우 Dp[n][1] -> 두 개의 방 중에 사자를 왼쪽 방에 넣은 경우 Dp[n][2] -> 두 개의 방 중에 사자를 오른쪽 방에 넣은 경우 즉, 이전 방의 경우의 수를 계속 취합해서 더할 수 있는습니다. 문제는 주어져있는 조건 "사자를 넣은 방에는 오른쪽방과 아랫방에는 넣을 수 없다" 라는 조건때문에, 사자를 넣지 않은 경우..

이번에 풀어볼 문제는 DP문제인 오르막 수입니다. 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수의 길이 N이 주어졌을 때, 오르막 수의 개수를 구하는 프로그램을 작성하시오. 수는 0으로 시작할 수 있다. www.acmicpc.net 이 문제에서 핵심적으로 봐야할 것은 이차원 배열을 통해서 이 문제를 이해하는 방식이라고 생각합니다. 제가 이 문제에서 사용한 방식은 DP[][] 이렇게 있을때 앞의 [] 배열은 N을 뜻하고 뒤의 배열은 [] N에 따라 붙는 한자리 숫자를 뜻합니다. 글로 표현하기가 어려워서 ..