1011: 징검다리
강을 건너기 위해서는 징검다리를 지나가야하는데, 징검다리에 씌여있는 숫자만큼의 금액을 징검다리를 건너는데 지불을 해야 한다. 징검다리를 건너가는데 드는 최소 비용을 구해주자
풀이
(이번 단계 최솟값) = (이전 3개 단계중 최솟값) + (이번 단계 비용)
1017: 돈을 줍자
길을 걷고 있는데, 천사가 나타나서 가는 길에 돈을 뿌려 놓았다. 그리고는 하는 말이 "마음껏 돈을 가져가세요, 하지만 연속해서 3개의 돈을 주우면 지옥에 가게 됩니다"
풀이
제한 조건은 3개 연속으로만 줍지 않으면 되기 때문에, 3칸을 한 단위로 하여 한 단위씩 기대최댓값을 구하면 된다
1055: 판 채우기
풀이
- P(0) = 1
- P(1) = 1
- P(n) = P(n-2) * 2 + P(n-1)
1056: 화장실 타일 채우기
풀이
- P(0) = 1
- P(1) = 1
- P(n) = P(n-2) + P(n-1)
1057: 걸기 쉬운 전화번호
풀이
- P[0][0], ..., P[0][9] = 1
- P[i][0] = P[i-1][8]
- P[i][1] = P[i-1][2] + P[i-1][4]
- P[i][2] = P[i-1][1] + P[i-1][3] + P[i-1][5]
- P[i][3] = P[i-1][2] + P[i-1][6]
- P[i][4] = P[i-1][1] + P[i-1][5] + P[i-1][7]
- P[i][5] = P[i-1][2] + P[i-1][4] + P[i-1][6] + P[i-1][8]
- P[i][6] = P[i-1][3] + P[i-1][5] + P[i-1][9]
- P[i][7] = P[i-1][4] + P[i-1][8]
- P[i][8] = P[i-1][5] + P[i-1][7] + P[i-1][9] + P[i-1][0]
- P[i][9] = P[i-1][6] + P[i-1][8]
1060: 팰린드롬 만들기
어떤 단어가 주어졌을 때, 이 단어를 팰린드롬으로 만들기 위해서는 최소 몇개의 글자를 더 추가하면 될까요?