DP
-
알고리즘: 백준 11048번 이동하기 (feat. python)알고리즘/백준(BaekJoon) 2020. 8. 27. 22:42
백준 11048번 링크입니다. 11048번: 이동하기 준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다. 준규는 �� www.acmicpc.net DFS 인줄 알았지만 시간초과가 나길래 다시 보니 다이나믹프로그래밍이였던 문제 dp를 이차원 리스트로 만들어서 dp[N][M] = (N, M)까지 오기까지의 합이라고 한다면 dp[N][M] = max(dp[N - 1][M], dp[N][M - 1], dp[N - 1][M - 1]) + maze[N][M] 라고 할 수 있다. import sys input = sys.stdin.readline N, M = map(in..
-
알고리즘: 백준 2293번 동전 1 (feat. python)알고리즘/백준(BaekJoon) 2020. 8. 25. 20:51
백준 2293번 링크입니다. 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 결론부터 말하면 dp를 이용해 풀어야 풀린다. 시간제한이 0.5초로 dp를 제외한 다른 방법을 쓰기가 까다롭다. 처음에는 dfs를 이용해 풀었지만 시간초과가 나길래 결국은 다른 분의 답을 참고하였다. import sys class Node: # 방문처리를 위해 노드 클래스를 만들었다. def __init__(self, data): self.data = data def dfs(start, tar..