본문 바로가기
반응형

{ Problem Solving }/Dynamic Programming20

[다이나믹 프로그래밍/파이썬] 백준 2533번 : 사회망 서비스(SNS) / 골드 3 https://www.acmicpc.net/problem/2533 2533번: 사회망 서비스(SNS) 페이스북, 트위터, 카카오톡과 같은 사회망 서비스(SNS)가 널리 사용됨에 따라, 사회망을 통하여 사람들이 어떻게 새로운 아이디어를 받아들이게 되는가를 이해하는 문제가 중요해졌다. 사회망 www.acmicpc.net import sys sys.setrecursionlimit(10**7) n = int(input()) graph = [[] for _ in range(n+1)] for i in range(n-1): u, v = map(int, sys.stdin.readline().split()) graph[u].append(v) graph[v].append(u) dp = [[0, 1] for _ in ran.. 2022. 4. 7.
[다이나믹 프로그래밍 / 파이썬] 백준 2342번 : Dance Dance Revolution / 골드 3 https://www.acmicpc.net/problem/2342 2342번: Dance Dance Revolution 입력은 지시 사항으로 이루어진다. 각각의 지시 사항은 하나의 수열로 이루어진다. 각각의 수열은 1, 2, 3, 4의 숫자들로 이루어지고, 이 숫자들은 각각의 방향을 나타낸다. 그리고 0은 수열의 마 www.acmicpc.net command = list(map(int, input().split())) def score(a, b): if a == 0: return 2 if a == b: return 1 if abs(a-b) % 2 == 1: return 3 if abs(a-b) % 2 == 0: return 4 inf = 9876543210 # dp[i][left][right] dp = .. 2022. 4. 4.
[다이나믹 프로그래밍] 백준 11049번 : 행렬 곱셈 순서 / 골드 3 https://www.acmicpc.net/problem/11049 11049번: 행렬 곱셈 순서 첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같 www.acmicpc.net n = int(input()) info = [] for _ in range(n): info.append(list(map(int, input().split()))) dp = [[0 for _ in range(n)] for _ in range(n+1)] for i in range(2, n+1): # i는 글자 수 for j in range(n-i+1): # j는 시작 인덱스 dp[i][j.. 2022. 4. 3.
[다이나믹 프로그래밍] 백준 1509번 : 팰린드롬 분할 / 골드 1 https://www.acmicpc.net/problem/1509 1509번: 팰린드롬 분할 세준이는 어떤 문자열을 팰린드롬으로 분할하려고 한다. 예를 들어, ABACABA를 팰린드롬으로 분할하면, {A, B, A, C, A, B, A}, {A, BACAB, A}, {ABA, C, ABA}, {ABACABA}등이 있다. 분할의 개수의 최솟값을 출력하 www.acmicpc.net text = input() n = len(text) table = [[False for _ in range(n)] for _ in range(n)] for i in range(n): table[i][i] = True for i in range(n-1): if text[i] == text[i+1]: table[i][i+1] = Tr.. 2022. 3. 31.
[다이나믹 프로그래밍/파이썬] 백준 1562번 : 계단 수 / 골드 1 https://www.acmicpc.net/problem/1562 1562번: 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net n = int(input()) dp = [[[0 for _ in range(1 2022. 3. 30.
[다이나믹 프로그래밍/파이썬] 백준 2098번 : 외판원 순회 / 골드 1 https://www.acmicpc.net/problem/2098 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net n = int(input()) board = [] for _ in range(n): board.append(list(map(int, input().split()))) dp = [[-1 for _ in range(1 2022. 3. 25.
반응형

티스토리툴바