목록다이나믹 (26)
정화 코딩
EDOC 2024-1 4회차 정모 (동적 계획법 알아보기 1)
A. 돌 게임 (백준 9655번) https://www.acmicpc.net/problem/9655 #python import sys input = sys.stdin.readline n = int(input()) if n % 2 == 0: print("CY") else: print("SK") 규칙을 찾으려고 몇 개 적어봤는데, 한 8까지 적어보니까 그냥 n이 홀수인 경우에는 상근이가 이기고 n이 짝수인 경우에는 창영이가 이기는 것 같은데..?? 라는 생각이 들었다. 뭔가 아닐 것 같지만 일단 한번 제출해봤는데 이왜진... (정답) B. 수열 (백준 2491번) https://www.acmicpc.net/problem/2491 #python import sys input = sys.stdin.readlin..
EDOC 2024-1 3회차 과제 (동적 계획법 알아보기 1)
11-1. 동적 계획법 알아보기 084. 1로 만들기 (백준 1463번) https://www.acmicpc.net/problem/1463 import sys input = sys.stdin.readline n = int(input()) num = [0 for _ in range(n + 1)] for i in range(2, n + 1): num[i] = num[i - 1] + 1 if i % 2 == 0: num[i] = min(num[i], (num[i // 2] + 1)) if i % 3 == 0: num[i] = min(num[i], (num[i // 3] + 1)) print(num[n]) 이전에 풀었던 문제. 간단한 다이나믹 문제였다. (정답) 085. 퇴사 (백준 14501번) https:/..
EDOC 2024-1 3회차 정모 (조합 알아보기 2)
A. 베라의 패션 (백준 15439번) https://www.acmicpc.net/problem/15439 #python import sys input = sys.stdin.readline n = int(input()) ans = n * (n - 1) print(ans) (정답) C. 격자상의 경로 (백준 10164번) #python import sys input = sys.stdin.readline n, m, k = map(int, input().split()) dp = [[0 for _ in range(n + m - 1)] for _ in range(n + m - 1)] ans = 0 dp[0][0] = 1 for i in range(1, n + m - 1): dp[i][0] = dp[i][i] = ..
EDOC 2024-1 2회차 과제 (조합 알아보기 2)
080. 조약돌 꺼내기 (백준 13251번) https://www.acmicpc.net/problem/13251 import sys input = sys.stdin.readline m = int(input()) # 조약돌 색 종류 color = list(map(int, input().split())) # 색 별 조약돌의 수 k = int(input()) # 뽑는 조약돌의 수 n = sum(color) # 전체 조약돌 수 ans = 0 for x in color: if x >= k: tmp = 1 for i in range(k): tmp *= ((x - i) / (n - i)) ans += tmp print(ans) 오잉 다이나믹도 아니고 조합 구할 필요도 없는 문제였잖아..???? 문제 풀기 전에 생각을..
EDOC 2024-1 2회차 정모 (조합 알아보기 1)
A. 다이나믹이 뭐예요? (백준 14494번) https://www.acmicpc.net/problem/14494 #python from sys import stdin # 점화식 : dp[i][j] = dp[i-1][j] + dp[i][j-1] + dp[i-1][j-1] mod = 1000000007 n, m = map(int, stdin.readline().split()) # n 가로 m 세로 dp = [[0 for _ in range(n + 1)] for _ in range (m + 1)] for i in range(1, n + 1): dp[1][i] = 1 for i in range(2, m + 1): dp[i][1] = 1 for j in range(2, n + 1): dp[i][j] = (dp[..
EDOC 2023-W 4회차 정모 (다익스트라 / 벨만-포드)
A. 지름길 (백준 1446번) https://www.acmicpc.net/problem/1446 #python from sys import stdin import sys from queue import PriorityQueue n, d = map(int, stdin.readline().split()) g = [[] for _ in range(10001)] visited = [False] * (10001) dst = [sys.maxsize] * (10001) que = PriorityQueue() for i in range(d): g[i].append((i+1, 1)) for _ in range(n): a, b, c = map(int, stdin.readline().split()) g[a].append(..
EDOC 2023-W 3회차 정모 (유니온 파인드 / 위상 정렬)
A. 여러분의 다리가 되어 드리겠습니다! (백준 17352번) https://www.acmicpc.net/problem/17352 #python from sys import stdin import sys sys.setrecursionlimit(100000) def find(a): if parent[a] == a: return a else: parent[a] = find(parent[a]) return parent[a] def union(a, b): a = find(a) b = find(b) if a != b: parent[b] = a n = int(stdin.readline()) parent = [i for i in range(n+1)] for _ in range(n-2): a, b = map(int, ..
EDOC 2023-W 2회차 과제 (유니온 파인드 / 위상 정렬)
08-2. 유니온 파인드 050. 집합의 표현 (백준 1717번) https://www.acmicpc.net/problem/1717 from sys import stdin def find(a): if parent[a] == a: return a else: parent[a] = find(parent[a]) return parent[a] def union(a, b): a = find(a) b = find(b) if a != b: parent[b] = a n, m = map(int, stdin.readline().split()) parent = [i for i in range(n+1)] for _ in range(m): x, a, b = map(int, stdin.readline().split()) if x ..