개발을항해

2011번: 암호코드 나올 수 있는 해석의 가짓수를 구하시오. 정답이 매우 클 수 있으므로, 1000000으로 나눈 나머지를 출력한다. 암호가 잘못되어 암호를 해석할 수 없는 경우에는 0을 출력한다. www.acmicpc.net POINT DP 암호는 두 자리로 묶을 수 있는 수가 있으면 경우의 수가 증가한다. 자릿수가 늘어나면서 동일한 방법으로 가짓수를 구하고 앞 자리의 결과가 뒤의 자리에도 영향을 미치니까 DP(Dynamic Programing, 다이나믹 프로그래밍)으로 문제를 해결한다. index 0 1 (시작) 2 3 4 5 code 0 2 5 1 1 4 dp 1 1 2 2 4 6 현재 자리를 i라고 하면, 다음과 같은 규칙이 생긴다. 뒤의 두 자리가 암호 범위에 속할 경우 dp[i] = dp[i..

https://www.acmicpc.net/problem/2210 2210번: 숫자판 점프 111111, 111112, 111121, 111211, 111212, 112111, 112121, 121111, 121112, 121211, 121212, 211111, 211121, 212111, 212121 이 가능한 경우들이다. www.acmicpc.net POINT 임의의 자리에서 상, 하, 좌, 우로 5번 이동하며 가능한 수의 개수를 구해야하기 때문에 DFS(Death-First Search)를 이용한다. 6자리의 000000 ~ 999999의 수가 만들어지므로 1000000자리의 visitied 배열을 사용한다. graph=[] for i in range(5): graph.append(list(map(..

2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net POINT Dynamic Programing (다이나믹 프로그래밍, dp) 피보나치 수열이 대표적인 예시이다. 1. 큰 문제를 작게 나눌 수 있고, 2. 작은 문제에서 구한 결과가 큰 문제에서도 사용되면 Dynamic Programing을 사용한다. 재귀(Top-down), 반복(Bottom-up) 두 가지 방법이 있으며, 시간 복잡도를 고려해서 반복문을 사용한다. 풀이 n = int(input()) # 계단 개수 scores = [0] * (n+1) # 계단 점수 for ..