본문 바로가기

백준33

백준 10971번 : 외판원 순회 2 (Python) 출처 : https://www.acmicpc.net/problem/10971 n = int(input()) graph = [list(map(int, input().split())) for _ in range(n)] min_cost = int(1e9) visited = [False] * n # now : 현재 방문 중인 도시 # now_cost : 지금 도시까지 비용 # visits_cnt : 지금까지 방문한 도시 수 def back_track(now, now_cost, visits_cnt) : global min_cost # 지금까지 비용이 최소 비용보다 크면 더 이상 탐색 X if now_cost >= min_cost : return # 모든 도시 다 방문하면 처음 시작한 도시로 돌아가야 함 if vi.. 2023. 1. 25.
백준 2206번 : 벽 부수고 이동하기 (Python) 출처 : https://www.acmicpc.net/problem/2206 from collections import deque # n : 행 개수 , m :열 개수 n, m = map(int, input().split()) graph = [list(input()) for _ in range(n)] # visited[0][x][y] : 벽을 안 부수고 (x, y)까지 최단거리 # visited[1][x][y] : 벽을 1회 부수고 (x, y)까지 최단거리 visited = [[[0] * m for _ in range(n)] for _ in range(2)] def bfs(start_x, start_y) : visited[0][start_x][start_y] = 1 move =[(0, 1), (0, -1).. 2023. 1. 19.
백준 1504번 : 특정한 최단 경로 (Python) 출처 : https://www.acmicpc.net/problem/1504 import heapq # import sys # input = sys.stdin.readline n, e = map(int, input().split()) graph = [[] for _ in range(n + 1)] for _ in range(e) : a, b, c = map(int, input().split()) graph[a].append((b, c)) graph[b].append((a, c)) # graph = [[], # [(2, 3), (3, 5), (4, 4)], # [(1, 3), (3, 3), (4, 5)], # [(2, 3), (4, 1), (1, 5)], # [(3, 1), (2, 5), (1, 4)]] v1.. 2023. 1. 2.
백준 11057 : 오르막 수 (Python) 출처 : https://www.acmicpc.net/problem/11057 n = int(input()) dp = [[0] * 10 for _ in range(n + 1)] dp[1] = [1] * 10 for i in range(2, n + 1) : for j in range(10) : dp[i][j] = sum(dp[i - 1][:j + 1]) print(sum(dp[-1]) % 10007) n자리의 오르막 수를 가정하면, 마지막 자리수가 0인 오르막 수는 마지막 자리수가 0인 n-1 자리의 오르막 수의 개수와 같다. 마지막 자리수가 1인 오르막 수는 마지막 자리수가 0, 1인 n-1 자리의 오르막 수의 개수의 합과 같다. 반복하면, 마지막 자리수가 9인 오르막 수는 마지막 자리수가 0~9인인 n-.. 2022. 12. 31.

티스토리툴바