![]()
https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 아이디어 DP 문제이다. 동전이 추가될 때 마다 추가된 경우의 수를 더해주면서 구한다. dp[0]을 1로 먼저 초기화하는 이유는 동전 본인의 인덱스의 경우 1을 더해줘야 하는데 (if j in coins) 이 부분을 없애고 점화식을 그대로 사용하기 위해서이다. (j-i가 0이 되므로 dp[0]인 1이 추가된다.) 0 1 2 3 4 5 6 7 8 9 10 1 1 1 1 1 1 1 1 1 1 1 1 2..
![]()
https://leetcode.com/problems/snakes-and-ladders/description/?envType=study-plan-v2&envId=top-interview-150 LeetCode - The World's Leading Online Programming Learning Platform Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 아이디어 BFS로 가장 짧은 이동 시간을 구하면 됐다. 2차원 리스트 보드판을 1차원으로 바꿔서 풀었다. 새 보드판 생성..
![]()
https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 아이디어 DP문제이다. 빨간색 표시한 자리를 [i][j]라고 할 때 [i][j]의 최댓값은 [i-1][j-1]과 [i-1][j] 중 큰 값과 [i][j]의 값을 더해서 구한다. 즉, 아래처럼 표현할 수 있다. dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + datas[i][j] 하지만 구한 식은 위 경우에 인덱스 에러를 일으키게 된다. 양 끝은 [i-1][j-1] 이 없거나, [i-1][j]가 없기 때문이다. 이를 해결하기 위한 두 가지 방..
https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 아이디어 그냥 구현하면 되는 문제였다!! 전체 코드 from queue import deque N, M, V = map(int, input().split()) tmp = [[int(x) for x in input().split()] for _ in range(M)] def dfs(x): visited[x] = 1 print(x, end=" ") if visit..
