Problem Solving94 [DP] 미로 탈출 미로 A에서 출발점은 A[0][0]이며 도착점은 A[N-1][M-1]이라 하자. 미로의 각 지점 A[i][j]를 지나갈 때 해당 지점의 값을 통행세로 내야한다. 미로의 각 지점에서는 오른쪽이나 아래쪽으로만 이동이 가능하다. N*M 크기의 미로에서 내야 하는 통행세의 최소값을 출력하시오. Input 첫째 줄에 미로의 행과 열의 크기 N, M이 주어진다. 둘째 줄부터 N개의 줄에 각 셀의 통행세가 M개 주어진다. 3 5 1 1 1 1 1 1 2 2 2 4 1 1 4 1 1 5 3 1 2 3 4 5 6 7 8 9 1 2 3 5 2 1 Output 첫째 줄에 주어진 미로에서 내야 하는 통행세의 최솟값을 출력한다. 8 18 import sys input=sys.stdin.readline n, m = map(int.. 2022. 12. 14. [DP] 계단 오르기 개구리가 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 점프하는 게임을 하려고 한다. 개구리는 한 계단을 점프해서 오를 수도 있고, 두 계단을 점프해서 오를 수도 있다. 각 계단에는 일정한 점수가 부여되어 있으므로, 개구리가 계단을 밟으면 그 계단의 점수를 획득한다. 예를 들어, 아래 그램에서 개구리가, 첫 번째, 두 번째, 네 번째, 여섯 번째 계단을 밟아 도착점에 도달하면 개구리가 획득하는 점수는 10 + 20 + 25 + 20 = 75점이 된다. N개의 계단에 부여된 점수가 주어질 때, 개구리가 획득할 수 있는 최대 점수를 출력하시오. Input 첫째 줄에 계단의 개수 N이 주어진다. 둘째 줄에 N개의 계단의 점수가 차례대로 주어진다. 6 10 20 15 25 10 20 6 10 -20 -1.. 2022. 12. 14. [DP] 이항 계수의 합 음이 아닌 정수 N이 주어졌을 때, 거듭제곱식 (1 + x)^N 를 전개했을 때의 각 항의 계수를 모두 더한 값을 출력하시오. 예를 들어, N=0인 경우에는 전개식 1 의 계수의 합은 1이다. N=1인 경우에는 전개식 1 + x 의 계수의 합은 1 + 1 = 2이다. N=2인 경우에는 전개식 1 + 2x + x^2 의 계수의 합은 1 + 2 + 1 = 4이다. N은 0보다 크거나 같고, 500,000보다 작거나 같은 정수이다. Hint: 이 문제는 해답 코드내에서 파스칼의 삼각형을 직접 생성하면 풀기 어렵지만, 먼저 규칙을 도출해서 간단한 해답 코드로 풀면 아주 쉬운 문제이다. Input 첫째 줄에 음이 아닌 정수 N이 주어진다. 0 2022. 12. 14. [DP] 세보나치 수열 DP: dynamic programming 미리 준비한 테이블을 통해 가장 작은 부분 문제를 먼저 풀고, 이미 해결한 부분 문제를 통해 상위 부분 문제를 풀어나가는 방식 세보나치 수열이란? F(1) = 1, F(2) = 2, F(3) = 3 F(n) = F(n-1) + F(n-2) + F(n-3), if n > 3 세보나치 수열은 다음과 같이 재귀적으로 정의한 수열이다. F(1) = 1, F(2) = 2, F(3) = 3 F(n) = F(n-1) + F(n-2) + F(n-3), if n > 3 양의 정수 n이 주어졌을 때, n번째 세보나치 수열 F(n)을 출력하시오. Input 첫째 줄에 양의 정수 n이 주어진다. 1 2022. 12. 14. 이전 1 ··· 18 19 20 21 22 23 24 다음