본문 바로가기
728x90

DP16

[python] 백준 1103 게임 문제 해결 DFS를 써야한다는 것은 쉽게 파악할 수 있다. 다만 떨어질 때 까지 옮겨지는 횟수를 세는 것으로 숫자가 커질 수 있으므로 dp를 사용하여한다. 숫자가 커지면 거의 DP를 사용해야 하는 것 같다. 한번 방문한 곳을 또 방문할 수 있으면 사이클을 돌 수 있고 무한반복이 가능하므로 -1을 출력하면 된다. 그렇지 않으면 떨어질 때 까지 혹은 방문한 지점이 나타날 때 까지 계속해서 DFS를 이용해서 나아가면 된다. CODE import sys input = sys.stdin.readline sys.setrecursionlimit(10**6) def dfs(sx, sy, cnt): global answer answer = max(answer, cnt) dxs = [1,-1,0,0] dys = [0,0,.. 2024. 1. 30.
[python] 백준 2533 사회망 서비스(SNS) https://www.acmicpc.net/problem/2533 2533번: 사회망 서비스(SNS) 페이스북, 트위터, 카카오톡과 같은 사회망 서비스(SNS)가 널리 사용됨에 따라, 사회망을 통하여 사람들이 어떻게 새로운 아이디어를 받아들이게 되는가를 이해하는 문제가 중요해졌다. 사회망 www.acmicpc.net 문제 해결 트리를 이용해야하는데 어떻게 이용해야할지 고민을 많이 했다. 부모-자식 중에서 적어도 한 명은 얼리 어답터여야한다. 따라서 dp를 이용해서 부모가 얼리 어답터일 때(dp[parent][1])일 때와 부모가 얼리 어답터가 아닐 때 (dp[parent][0])를 구분을 해서 알고리즘을 풀어나가면 되겠다라는 생각을 한다. dp[i][j]는 i번째 노드가 j상태일때 i번째 밑에 있는 노드.. 2023. 9. 27.
[python] 백준 9084 동전 https://www.acmicpc.net/problem/9084 9084번: 동전 우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 예를 들어, 30원을 만들기 위해서는 www.acmicpc.net 문제 해결 dp[i]는 i원을 만드는데 가지수를 나타내는 것이다. 1원부터 $10^{4}$까지 차례로 dp를 통해 나타낸다. 동전이 있는것은 1개로 되므로 dp[coin]은 1이상이다. CODE for _ in range(int(input())): n = int(input()) coins = list(map(int, input().split())) total = int(input(.. 2023. 3. 22.
[python] 백준 1495 기타리스트 https://www.acmicpc.net/problem/1495 1495번: 기타리스트 첫째 줄에 N, S, M이 주어진다. (1 ≤ N ≤ 50, 1 ≤ M ≤ 1,000, 0 ≤ S ≤ M) 둘째 줄에는 각 곡이 시작하기 전에 줄 수 있는 볼륨의 차이가 주어진다. 이 값은 1보다 크거나 같고, M보다 작거나 같다. www.acmicpc.net 문제 해결 전형적인 DP문제 dp[i][j]를 i번째 볼륨조절 후 j의 볼륨 가능 유무로 정의할 수 있다. CODE import sys input = sys.stdin.readline n, s, m = map(int, input().split()) # 곡 개수, 시작 볼륨, 최대 볼륨 V = [0] + list(map(int, input().split())) .. 2023. 3. 20.
728x90