Don't die there

문제 링크 https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net N이 2일 때는 와인의 첫번째와 두번째 값을 더한 값입니다. N이 3이상일 때는 위와 같이 연속되는 값이 3개가 넘지않는 경우 중 총 3가지의 값 중 최대값이 정답이 됩니다. 구현 코드

문제 링크 https://www.acmicpc.net/problem/9465 9465번: 스티커 문제 상근이의 여동생 상냥이는 문방구에서 스티커 2n개를 구매했다. 스티커는 그림 (a)와 같이 2행 n열로 배치되어 있다. 상냥이는 스티커를 이용해 책상을 꾸미려고 한다. 상냥이가 구매한 스티 www.acmicpc.net N이 1일 때는 아래, 위의 두 값 중 최대값이 되고 2일 때는 이전 대각선과의 합 중 최대값이 됩니다. 3이상일 때는 이전 대각선과의 합과 이전 대각선 왼쪽과의 합 중 최대값이 정답이 됩니다. 구현 코드

문제 링크 https://www.acmicpc.net/problem/2193 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net N이 1일 때는 1, 2일때 1가지의 방법이 있습니다. N이 3이상일 때부터는 N-1에서 오른쪽에 0을 더한 방법과 N-2에서 오른쪽에 01을 더한 방법의 합이 됩니다. 따라서 DP(N) = DP(N-1) + DP(N-2)로 구할 수 있습니다. 구현 코드

문제링크 https://www.acmicpc.net/problem/11057 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수� www.acmicpc.net N이 1일 때는 0~9 까지 10가지 방법이 있습니다. N이 2이상일 때는 0~9까지 가장 오른쪽 숫자보다 작거나 같은 숫자들의 방법을 모두 더한 값입니다. 예를들어 N이 3일 때 마지막 숫자가 1이면 001, 011, 111로 3가지가 나오고 마지막 숫자가 2이면 002, 012, 112, 122, 222로 5가지가 나옵니다. 이러한 방법으로 마지막..

문제 링크 https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net N이 1일 때는 1부터 9까지 총 9가지 계단이 있습니다. N이 2일 때 부터는 오른쪽 숫자를 기준으로 0일 때는 왼쪽에서 1 밖에 오지 못하므로 10 한개 1~8일 때는 (21, 31), (12, 32), (23, 43), ... 과 같이 왼쪽에서 -1과 +1의 숫자가 올 수 있습니다. 9일 때는 왼쪽에서 8 밖에 오지 못하므로 89 한개로 완성됩니다. 따라서 다음 점화식으로 총 계단 수를 구할 수 있습니다. d[N][M] (M = 0~9) = if M = 0 then d[N-1][M+1] if M..

문제 링크 https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 문제 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 1+1+1+1 1+1+2 1+2+1 2+1+1 2+2 1+3 3+1 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 www.acmicpc.net N이 1일 때는 1, 2일 때는 2, 3일 때는 4가지 방법이 있습니다. N이 4일 때는 3일 때에서 1씩 더하는 방법 2일 때에서 2씩 더하는 방법 1일 때에서 3씩 더하는 방법이 총 방법의 수 입니다. N이 5일 때도 마찬가지로 N이 2, 3, 4일 때의 방법의 합과 같습니다. 따라서 N이 4 이상일 때에는 dp..

문제 링크 https://www.acmicpc.net/problem/11727 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net 이전 문제와 동일하게 규칙만 찾아내면 구현할 수 있습니다. N이 1일때는 여전히 1가지 방법밖에 없지만 N이 2인경우 2x2 도형이 하나 추가되어 3가지 방법이 생깁니다. N이 3 이후일때는 N-1 의 도형에서 오른쪽에 2x1 세로 도형이 한 개 붙은 형태와 N-2 의 도형에서 오른쪽에 1x2 가로 도형이 두 개 붙은 형태, 2x2 타일이 한 개 붙은 형태로 완성이 됩니다. 따라서 N은 dp(N-1) + dp(N-2..

문제 링크 https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 위 그림으로 봤을 때 N이 1일때는 방법이 한가지, 2일때는 두가지의 방법이 있습니다. N이 3 이후일때는 N-2 의 도형에서 가로 두 개의 도형이 오른쪽에 붙은 형태와 N-1 의 도형에서 세로 한 개의 도형이 오른쪽에 붙은 형태로 완성이 됩니다. 이를 통해 N은 dp(N-1) + dp(N-2) 로 구할 수 있다는걸 알 수 있습니다. 구현 코드