본문 바로가기

PS73

[테스트케이스 추가] 백준 16681: 등산 66%에서 시간초과나는 경우 python, 파이썬 1. 문제 https://www.acmicpc.net/problem/16681 16681번: 등산 첫 번째 줄에 지도에 표시된 지점의 개수, 지점을 잇는 경로의 개수, 주환이의 거리 비례 체력 소모량, 높이 비례 성취감 획득량을 나타내는 정수 N, M, D, E가 공백을 사이에 두고 주어진다. (2 ≤ www.acmicpc.net 2. 풀이 고생을 좀 했는데, 핵심은 (1) 체력을 최소한으로 하는 dijkstra를 찾는다. 성취도와 계산하는 것은 최단거리를 찾은 후에 해도 된다. (이걸 생각하기가 어려웠다) (2) 모든 dijkstra를 찾지 말고 넘어가는 코드를 넣어야한다. (3) 올라갈 때 1->k 와 내려갈때 k->n을 다익스트라 하나의 코드로 작성할 수 있다는 것이다. dijk(1) 이랑 dijk.. 2021. 7. 6.
[테스트케이스 추가] 백준 1261번: 알고스팟 (python, 파이썬) 1. 문제 https://www.acmicpc.net/problem/1261 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net 2. 풀이 1) input을 받을 때 split()을 하지 못하는 것과 readline을 하면 줄바꿈('\n')이 함께 들어온다는 것을 명심해야한다. 2) N과 M은 둘이 서로 다른 예시를 넣어서 index 에러로 빠르게 확인한다. 3. 구현 import sys import heapq import math sys.stdin=open('input.txt') dr = .. 2021. 7. 5.
[테스트케이스 추가] 백준 1916 최소비용 구하기 (python, 파이썬) 1. 문제 https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 2. 풀이 다익스트라! 3. 구현 import sys import heapq import math # sys.stdin=open("input.txt") N = int(sys.stdin.readline()) bus = int(sys.stdin.readline()) gph=[[] for _ in range(N+2)] dist=[math.inf for _ i.. 2021. 7. 5.
[테스트케이스 추가] 백준 4485번 녹색 옷 입은 애가 젤다지? (python, 파이썬) 1. 문제 https://www.acmicpc.net/problem/4485 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net 2. 풀이 주어진 지도가 graph라고 생각하고 dist도 같은 모양으로 만들어서 상하좌우를 순회한다. 3. 구현 import sys import heapq import math sys.stdin=open('input.txt') dr = [0,1,0,-1] dc = [1,0,-1,0] def valid(r,c,len): return r>=0 and c>=0 and r 2021. 7. 5.
반응형

티스토리툴바