Algorithm475 [파이썬] 백준 10217 : KCM Travel (플레5) [파이썬] 백준 10217 : KCM Travel (플레5) 10217번: KCM Travel 각고의 노력 끝에 찬민이는 2014 Google Code Jam World Finals에 진출하게 되었다. 구글에서 온 초대장을 받고 기뻐했던 것도 잠시, 찬찬히 읽어보던 찬민이는 중요한 사실을 알아차렸다. 최근의 대세에 www.acmicpc.net 문제 풀이 방향성 생각 다익스트라 + 2차원 visit (노드, 사용금액) = 시간기록 node가 100 / 지원비용 10000 = 100만이라서 메모리가 좀 빡빡해보인다 -> 당연하게도(?) 터져버림 최대로 지원금이 m으로 정해짐 -> 냅색? (사실 DP 태그보고 알았음 ㅋㅋ) 전체코드 import sys input = lambda : sys.stdin.readl.. 2023. 12. 25. [파이썬] 백준 1162 : 도로포장 (플레5) [파이썬] 백준 1162 : 도로포장 (플레5) 1162번: 도로포장 첫 줄에는 도시의 수 N(1 ≤ N ≤ 10,000)과 도로의 수 M(1 ≤ M ≤ 50,000)과 포장할 도로의 수 K(1 ≤ K ≤ 20)가 공백으로 구분되어 주어진다. M개의 줄에 대해 도로가 연결하는 두 도시와 도로를 통과하 www.acmicpc.net 문제 풀이 0. 방향성 생각 상태 나누기 + 다익스트라 벽뿌 시리즈에서 벽을 부순 횟수로 상태 나눈 것 처럼, 도로를 포장한 횟수를 힙에 추가적으로 넣어서 풀이. 태그에 DP가 달려있긴 한데 기본적인 발상이 다익이랑 똑같다. 1. 입력 import heapq as hq import sys input = lambda : sys.stdin.readline().rstrip() n,m,.. 2023. 12. 25. [파이썬] 백준 15806 : 영우의 기숙사 청소 (플레5) [파이썬] 백준 15806 : 영우의 기숙사 청소 (플레5) 15806번: 영우의 기숙사 청소 통학이 너무나도 하기 싫었던 영우는 결국 학교의 기숙사에 들어갔다. 통학의 고통에서 해방된 기쁨도 잠시, 학교 기숙사에서는 일정 기간마다 청소 검사를 한다는 사실을 알게 되었다. 청소 검 www.acmicpc.net 문제 풀이 0. 방향성 생각 그림2의 (a) (b)의 시작 곰팡이 위치를 보면 서로 교차해서 나타나는 것을 확인할 수 있다. 홀수일에 피는 곰팡이, 짝수초에 피는 곰팡이, 항상 피어있는 곰팡이로 구분한다. 예제 1번의 테케를 보면 곰팡이가 중앙에서 피어서 증식하지 못하는 경우도 생긴다. 입력에 추가하기 전, n = 1,2거나 n=3의 중심처럼 곰팡이가 증식하지 못하는 엣지케이스 잡아내기 1. 입력 .. 2023. 12. 23. [파이썬] 백준 1102 : 발전소 (플레5) [파이썬] 백준 1102 : 발전소 (플레5) 1102번: 발전소 첫째 줄에 발전소의 개수 N이 주어진다. N은 16보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 발전소 i를 이용해서 발전소 j를 재시작할 때 드는 비용이 주어진다. i줄의 j번째 값이 그 www.acmicpc.net 문제 풀이 0. 방향성 생각 dfs로 순회해주면서 가지치기 / 메모제이션으로 시간 단축하기. 개수가 다 채워졌으면 다른 발전소를 키지 않는거는 자명한 사실이니까, 개수 체크해주기. 1. 입력 import sys input = lambda : sys.stdin.readline().rstrip() sys.setrecursionlimit(10**6) def cvt(state): on = 0 string = '' for .. 2023. 12. 22. 이전 1 ··· 59 60 61 62 63 64 65 ··· 119 다음
