BOJ 2156 포도주시식

문제출저

효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규칙이 있다.

포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다.
연속으로 놓여 있는 3잔을 모두 마실 수는 없다.
효주는 될 수 있는 대로 많은 양의 포도주를 맛보기 위해서 어떤 포도주 잔을 선택해야 할지 고민하고 있다. 1부터 n까지의 번호가 붙어 있는 n개의 포도주 잔이 순서대로 테이블 위에 놓여 있고, 각 포도주 잔에 들어있는 포도주의 양이 주어졌을 때, 효주를 도와 가장 많은 양의 포도주를 마실 수 있도록 하는 프로그램을 작성하시오.

예를 들어 6개의 포도주 잔이 있고, 각각의 잔에 순서대로 6, 10, 13, 9, 8, 1 만큼의 포도주가 들어 있을 때, 첫 번째, 두 번째, 네 번째, 다섯 번째 포도주 잔을 선택하면 총 포도주 양이 33으로 최대로 마실 수 있다.

풀이

세번 연속해서 포도주를 마실 수 없는 조건에 주목하여 경우이 수를 우선 생각해본다.
현재 위치를 i라고 할때,
1)　i번째 포도주를 마시지 않는 경우
2)　i번째 포도주를 마시고 이전 포도주는 마시지 않는 경우(1연속)
3))　i번째 포도주를 마시고 이전 포도주도 마신 경우(2연속)

총 3가지의 상황을 고려할 수 있다. 그래서 int형 배열 dp[i][3] 배열을 이용하여 문제를 풀었다.

  • dp[i][0] : i번째 순서에서 포도주를 마시지 않았을때 1~i번째까지 마신 최대의 포도주의 양
    i번째 순서에서 포도주를 마시지 않았다면 이전 상황은 포도주를 마시던 마지시않던 전혀 상관이 없다.
    그래서 do[i][0]의 값은 dp[i-1][0], dp[i-1][1], dp[i-1][2]중 최대값이 될것이다.

  • dp[i][1] : i번째 순서에서 포도주를 마시고, i-1번째의 포도주는 마시지 않았을때(1연속) 1~i번째까지 마신 최대의 포도주양
    i-1번째에서 포도주를 마시지 않았으므로 dp[i][1]의 값은 dp[i-1][1] + wine[i] 이 된다.

  • dp[i][2] : i번째 순서에서 포도주를 마시고, i-1번째 포도주도 마셨을때(2연속) 1~i번쨰까지 마신 최대의 포도주양
    i-1번째에서 포도주를 마셨으므로 dp[i][2]의 값은 dp[i-1][1] + wine[i]이 된다.

초기값 dp[1][0] = 0, dp[1][1] = wine[1], dp[1][2] = wine[1]로 세팅해준다음 n까지 dp배열값을 채워나가면 문제를 해결할 수 있다.

최종적으로 n번째 마신 포도주의 최대의 양은 dp[n][0], dp[n][1], dp[n][2] 중의 최댓값이 된다.

소스코드

전체소스

BOJ 10844 쉬운 계단수

문제출저

45656이란 수를 보자.

이 수는 인접한 모든 자리수의 차이가 1이 난다. 이런 수를 계단 수라고 한다.

세준이는 수의 길이가 N인 계단 수가 몇 개 있는지 궁금해졌다.

N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구하는 프로그램을 작성하시오. (0으로 시작하는 수는 없다.

풀이

오르막수문제의 약간 더 심화된 버전(?)

예시로 주어진 수 45656을 뒤에서 부터 살펴보자. 마지막 자리수 6전에 올 수 있는 수는 5 혹은 7이 된다. 그리고 마지막 전의 숫자 5 전에 올 수 있는 수는 4혹은 6이 되고 앞의 자리수도 이와 같이 경우의 수를 생각해 줄 수 있다.
그러면 길이가 l이고 현재 수가 i일때 이 수가 만들어질 수 있는 경우의수는 길이가 l-1이고 i-1 (i보다 1작은 수)로 끝나는 수가 만들어지는 경우의 수와 길이가 l-1이고 i+1 (i보다 1큰수)로 끝나는 수가 만들어지는 경우의 수의 합이 된다.
그러면 아래와 같은 식을 도출할 수 있다.
-> dp[l][i] = dp[l-1][i-1] + dp[l-1][i+1]

길이가 1이고 i로 시작할 경우 dp[1][i]의 값은 각각 1이 될것이다.(한자리의 수이므로)
이제 이걸 이용해서 dp[n][i] (i = 0~9) 값을 범위를 고려해주면서 채워주면 최종적으로 원하는 값을 얻을 수 있다.
주의할 점은 계단수가 0으로 시작할 수는 없지만 101와 같이 1로 시작하는 다음자리수로 0이 올수있다는점을 생각해줘야한다.

소스코드

전체소스

			int[][] dp = new int[n + 1][10];
			for (int i = 0; i <= 9; i++) {
				dp[1][i] = 1;
			}
			for (int l = 2; l <= n; l++) {
				for (int i = 0; i <= 9; i++) {
					if (i - 1 >= 0) {
						dp[l][i] += dp[l - 1][i - 1];
					}
					if (i + 1 <= 9) {
						dp[l][i] += dp[l - 1][i + 1];
					}
					dp[l][i] %= 1000000000;

				}
			}