시작이 반

https://www.acmicpc.net/problem/11657 11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. www.acmicpc.net 문제 N개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 버스가 M개 있다. 각 버스는 A, B, C로 나타낼 수 있는데, A는 시작도시, B는 도착도시, C는 버스를 타고 이동하는데 걸리는 시간이다. 시간 C가 양수가 아닌 경우가 있다. C = 0인 경우는 순간 이동을 하는 경우, C < 0인 경우는 타임머신으로 시..

구현, 시뮬레이션 문제이다. BFS를 이용하여 풀 수 있다. 우선 BFS를 사용하여 최단 거리에 있는 사람을 찾는다. 1. 최단거리에 있는 사람을 찾고 그 거리를 저장한다. 2. 사람을 태우고 목적지까지 다시 BFS를 이용하여 거리를 저장한다. 만약 사람이나 목적지까지 도달할 수 없으면 그즉시 종료하고 -1을 출력한다. 도달할 수 있다면 연료에서 1번을 뺏을때 음수가 나오면 종료하고 -1을 출력한다. 연료에서 1번을 뺏을때 양수면 다시 2번을 빼고 뺏을때 음수면 종료하고 -1을 출력한다. 종료가 안됐으면 연료에 2번 *2 를 더한다. 모든 사람을 태웠으면 종료하고 남은 연료를 본다. import math from collections import deque n, m, energy = map(int, in..

구현, 시뮬레이션 문제이다. 이 문제는 특정 알고리즘을 사용하는 것이 아닌 모든 경우에 대해서 완전탐색을 하면된다. 구할 수 있는 모든 경우의 경계선을 구하고 5개의 구역의 최대 인구와 최소 인구의 차를 구한다. 조건과 인덱스만 잘 확인해주면 쉽게 풀 수 있다. 이 문제는 인덱스가 1,1 ~ n, n까지다. import math n = int(input()) a = [list(map(int, input().split(' '))) for _ in range(n)] answer = math.inf def div_area(): for i in range(n): for j in range(n): x, y = i, j for d1 in range(1, n - 1): for d2 in range(1, n - 1):..

DP 또는 완탐으로 풀수 있다. 완탐으로 문제를 해결하였다. 해당 숫자의 int(제곱근)부터 해당 숫자 - int(제곱근)^2 의 제곱근-1까지 반복문을 돌려서 확인하였다. 사실 그냥 해당 숫자의 int(제곱근)부터 0까지 돌려도 풀린다. import math n = int(input()) answer = 4 def solve(): global answer, n sqrt = int(math.sqrt(n)) for i in range(sqrt, int(math.sqrt(n - sqrt ** 2)) - 1, -1): n -= i ** 2 if n == 0: answer = min(1, answer) sqrt2 = int(math.sqrt(n)) for j in range(sqrt2, int(math.sqrt..

수빈이가 다음 장소로 갈 경우는 3가지이다. x-1, x+1, 2x 하지만 x-1, x+1 의 경우는 시간이 1초가 걸리고 2x 는 0초가 걸린다. 즉 다익스트라 알고리즘을 사용하여 문제를 풀 수 있다. ( 각 경우로 갈 시간이 같다면 Bfs로 풀 수 있다. ) import heapq import math n, k = map(int, input().split(' ')) dist = [math.inf] * 100001 dx = [-1, 1, 2] p_queue = list() def dijkstra(start): dist[start] = 0 heapq.heappush(p_queue, (dist[start], start)) while p_queue: pop_dist, pop_vertex = heapq.hea..

구현, 시뮬레이션 문제이다. 여기서 생각해 봐야할 것은 1. 어떻게 숫자를 세고 센 숫자를 적은 숫자 부터 넣을것인지 2. 행에 대해서의 계산은 쉽지만 열에 대한 계산을 어떻게 할것인지 이 2가지이다. 1번 이 문제는 사전을 사용하였다. 각 숫자에 대해 key로 사용하였으며 나온 횟수를 value로 사용하였다. 그 후에 value를 기준으로 큰것부터 정렬을 하였다. 사전을 정렬하면 [(key, vlaue)] 형식의 리스트가 나온다. 그 다음으로는 리스트의 값을 pop하면서 다시 새로운 2차원 리스트를 만들어줬다. 2번 이 문제는 일단 열을 보면서 반복을 하는데 새로운 2차원 리스트의 행에 넣어준다. 그 후에 만들어진 새로운 리스트의 x, y 값을 다시 새로운 리스트를 만들어 y, x 좌표에 넣어준다. r..

구현, 시뮬레이션 문제이다. 여기서 필요한 알고리즘은 BFS, BackTracking이다. BFS는 궁수가 최단 거리에있는 적을 죽일때 필요하며 BackTracking은 궁수의 배치에대한 조합을 구할때 필요하다. 궁수는 3명을 배치한다. 즉, 열의 개수가 m 이기 때문에 mC3 의 조합이 필요하다 두개의 알고리즘을 사용하고 실수만 하지 않으면 풀수 있을 것이다. import heapq from collections import deque n, m, d = map(int, input().split(' ')) graph = [list(map(int, input().split(' '))) for _ in range(n)] visitied = [False] * m max_kill = 0 def combinati..

구현, 시뮬레이션 문제이다. 시간제한을 보면 파이썬은 1.3초안에 통과해야한다... 엄청 빡세다.. 사실 알고리즘은 필요로 하지 않는 문제이다. 하지만 시간초과로인해 고려해야 할 점이 많았다. 처음 접근한 방식은 나무에 대한 좌표와 나이를 묶어서 deque에 넣으면서 확인을 하였다. from collections import deque n, m, k = map(int, input().split(' ')) a = [list(map(int, input().split(' '))) for _ in range(n)] graph = [[5] * n for _ in range(n)] trees = deque() #나무들이 들어있는 deque dead_trees = list() for _ in range(m): x, ..