Study Log Study Log

https://www.acmicpc.net/problem/1890 # 1890 : 점프 import sys n = int(sys.stdin.readline()) game = [list(map(int, sys.stdin.readline().split())) for _ in range(n)] # dp 테이블 dp = [[0] * n for _ in range(n)] dp[0][0] = 1 # 반복문을 통해 갈 수 있는 그래프의 좌표를 탐색 for i in range(n): for j in range(n): # 오른쪽 끝 점이면 중지 if i == n - 1 and j == n - 1: print(dp[i][j]) break # 오른쪽으로 이동 if j + game[i][j] < n: dp[i][j + gam..

https://www.acmicpc.net/problem/10164 count는 k를 찾기 위해 설정k가 0이 아니면 k까지 가는 경우의 수와 k부터 끝점까지 가는 경우의 수를 곱해주면 된다. # 10164 : 격자상의 경로 import sys input = sys.stdin.readline n, m, k = map(int, input().rstrip().split()) dp = [[0] * (m + 1) for _ in range(n + 1)] dp[0][1], count = 1, 1 for i in range(1, n + 1): for j in range(1, m + 1): # k일 시 현재 위치 저장 if count == k: sx = i sy = j # k 찾기 위해 1씩 증가 count += 1..

https://www.acmicpc.net/problem/11048 3방향 중 사탕을 최대로 먹을 수 있는 경우와 이전 위치의 사탕값을 더해서 점화식을 작성하면 풀리는 문제였다. 소스코드# 11048 : 이동하기 import sys input = sys.stdin.readline n, m = map(int, input().split()) maze = [list(map(int, input().rstrip().split())) for _ in range(n)] # dp 테이블 설정 dp = [[0] * (m + 1) for _ in range(n + 1)] for i in range(1, n + 1): for j in range(1, m + 1): # d[i - 1][j] : ↓ # d[i][j - 1] :..

https://www.acmicpc.net/problem/2293 소스코드# 2293 : 동전 1 n, k = map(int, input().split()) coins = [int(input()) for _ in range(n)] # dp 테이블 초기화 dp = [0] * (k + 1) dp[0] = 1 for coin in coins: for i in range(k + 1): # 만들려고 하는 돈이 가지고 있는 화페단위보다 크거나 같을 경우 if i >= coin: # 이전 경우의 수에 현재 동전으로 만들 수 있는 경우의 수 더하기 dp[i] += dp[i - coin] print(dp[k]) 백준 9084번과 비슷한 문제였고, 실제로 동일한 코드로 풀린 문제이다. 그때도 구글링해서 풀었는데, 이번에도..

https://www.acmicpc.net/problem/1965 처음에 문제가 잘 이해가 안되서 구글링을 통해 다른 사람들의 풀이를 참고해서 풀었다. 이중 for문을 사용하여 현재 상자 위치에서 그 앞에 더 작은 상자가 있다면 그 상자를 현재 상자에 넣는 경우와 현재 dp 테이블 값 중 최댓값을 다시 dp 테이블에 넣는 식으로 풀면 된다. # 1965 : 상자 넣기 n = int(input()) box = list(map(int, input().split())) # dp 테이블 1로 초기화 d = [1] * 1001 for i in range(1, n): for j in range(i): # 현재 위치에서 더 작은 상자가 있을 시 if box[j] < box[i]: d[i] = max(d[i], d[j..

https://www.acmicpc.net/problem/9084 이코테 다이나믹 프로그래밍의 효율적인 화페 구성 문제와 같은 줄 알고 동일하게 풀었으나 틀렸다,,다른 방법이 떠오르지 않아 결국 구글링을 하게 되었다. 틀린 코드t = int(input()) for _ in range(t): n = int(input()) money = list(map(int, input().split())) m = int(input()) # dp 테이블 초기화 d = [10001] * (m + 1) d[0] = 1 for i in range(n): for j in range(money[i], m + 1): d[j] = min(d[j], d[j - money[i]] + 1) print(d[m]) 만들려고 하는 돈이 가지고 ..

https://www.acmicpc.net/problem/14494 다이나나믹 프로그래밍으로 풀기 위해 점화식은 세웠는데, 초기값을 잘못 설정해서 답이 0이 나왔었다,,, 구글링을 통해 다른 사람들이 문제 푼 것을 참고하여 해결했다. # 11494 : 다이나믹이 뭐예요? import sys input = sys.stdin.readline n, m = map(int, input().rstrip().split()) # dp 테이블 초기화 d = [[0] * (m + 1) for _ in range(n + 1)] d[0][0] = 1 for i in range(1, n + 1): for j in range(1, m + 1): # d[i - 1][j] : ↓ # d[i][j - 1] : → # d[i - 1][..

https://www.acmicpc.net/problem/13301 피보나치 수열로 만드는 타일이라 점화식 세우는 것은 편했다. 직사각형 넓이는 이전항 + 현재항을 가로로, 현재항을 세로로 가정해서 식을 세웠다. # 13301 : 타일 장식물 n = int(input()) # dp 테이블 초기화 d = [0] * 81 d[1] = 1 d[2] = 1 for i in range(3, n + 1): # 피보나치 수열 점화식 d[i] = d[i - 1] + d[i - 2] # 직사각형 넓이 출력 print((d[n] + d[n] + d[n - 1]) * 2) Uploaded by Notion2Tistory v1.1.0