본문 바로가기

Algorithm/Dynamic Programming69

[파이썬] 백준 2098 : 외판원 순회 (골드1) [파이썬] 백준 2098 : 외판원 순회 (골드1) 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 문제 풀이 0. 방향성 생각 상태가 많이 존재 -> 비트마스킹 경로 탐색 -> BFS 1. 입력 import sys sys.setrecursionlimit(10**6) n = int(input()) w = {i:dict(zip(range(n),list(map(int,input().split())))) for i in range(n)} dp = [[-1]*(n) for _ i.. 2023. 8. 30.
[파이썬] 백준 1103 : 게임 (골드2) [파이썬] 백준 1103 : 게임 (골드2) 1103번: 게임 줄에 보드의 세로 크기 N과 가로 크기 M이 주어진다. 이 값은 모두 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 보드의 상태가 주어진다. 쓰여 있는 숫자는 1부터 9까지의 자연수 또는 www.acmicpc.net 문제 풀이 0. 방향성 생각 DFS + DP 사용 1. 입력 import sys sys.setrecursionlimit(10**6) input = lambda : sys.stdin.readline().rstrip() h,w = map(int,input().split()) arr = [list(input()) for _ in range(h)] dp = [[-1]*w for _ in range(h)] visit = [[0.. 2023. 8. 29.
[파이썬] 백준 2096: 내려가기 (골드5) [파이썬] 백준 2096: 내려가기 (골드5) 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 문제 풀이 0. 방향성 생각 메모리가 4MB이다. 3*N 리스트를 작성하지 않고 현재 최대값, 최소값만 기억한다. 1. 입력 import sys input = lambda : sys.stdin.readline().rstrip() n = int(input()) arr_max,arr_min = [0]*3,[0]*3 temp_max,temp_min = [0]*3,[0]*3 for문을 돌면서 현재 arr_max, arr_min을 업데이트.. 2023. 8. 22.
[파이썬] 백준 3687: 성냥개비 (골드2) [파이썬] 백준 3687: 성냥개비 (골드2) 3687번: 성냥개비 각 테스트 케이스에 대해서 입력으로 주어진 성냥개비를 모두 사용해서 만들 수 있는 가장 작은 수와 가장 큰 수를 출력한다. 두 숫자는 모두 양수이어야 하고, 숫자는 0으로 시작할 수 없다. www.acmicpc.net 문제 풀이 0. 방향성 생각 최대값은 가장 적은 수를 사용해서 앞에 붙여서 가장 큰 자리수로 만들어준다. 최소값은 DP를 사용해서 자연수 n = k + (n-k)로 분리한다. 1. 입력 import sys input = lambda : sys.stdin.readline().rstrip() use = [int(input()) for _ in range(int(input()))] dp = [0]*101 dp[:10] = [0,.. 2023. 8. 22.

티스토리툴바