친절한 도현씨 친절한 도현씨

(python 풀이가 하나도 존재하지 않아서 이 글을 써 봅니다.) ★ 접근 기다리기, a만큼 새치기, b만큼 새치기 3가지 경우를 혼합하여 최소한의 횟수로 앞으로 가야하는 상황입니다. 보통 이 상황에서 bfs를 떠올립니다. 필자도 bfs를 떠올렸지만 n의 최대 크기 때문에 불안한 감이 있었습니다. 역시나 시간 초과가 나왔고 dp로 풀기로 했습니다. ★ 풀이 (1로 만들기 문제와 다른 점이 하나 없습니다.) 1. 1,a+1, b+1을 0보다 크거나 같은 상황에서 빼면서 최소값을 구해나가면 된다. ★ 코드 from collections import deque import sys input = sys.stdin.readline n,a,b = map(int,input().split()) dp = [float(..

★ 접근 문제를 보면 4방향으로 이동하면서 탐색하는 백트래킹을 떠올리기 쉽다. 하지만 n의 최대 크기가 10이고 방문했던 곳을 무한히 방문할 수 있기 때문에 백트래킹을 한다면 시간초과가 난다. 그렇다면 어떻게 해야할까? 우유가 있는 좌표를 따로 담아 놓는 백트래킹을 해야한다. ★ 풀이 1. 진우의 초기 좌표와 우유들이 있는 좌표를 구한다. 2. for i in range(len(mint)): 우유들을 처음부터 하나씩 꺼내보면서 if not visited[i]: 방문하지 않았으면서 현재 체력으로 꺼낸 우유 좌표까지 도달할 수 있다면 그 지역까지 가면서 dfs를 해주면 된다. ★ 코드 import sys input = sys.stdin.readline n,m,h = map(int,input().split()..

★ 접근 처음에는 단순하게 문제를 보고 bfs를 떠올렸다. 문제가 bfs를 떠올리게 유도했기 때문에 대부분의 사람들도 처음에 bfs를 떠올릴 수 밖에 없다고 생각한다. 그러나 구현을 하다보면 bfs로(풀 수도 있겠지만 필자는 실력이 부족해서 구현할 수가 없다) 풀기에는 쉽지 않다는 것을 떠올렸고 생각하면 할 수록 dp로 나를 이끌었다. ★ 풀이 1. 일단 토끼가 있던 위치를 찾아주고 해당 좌표에 dp를 0으로 처리함으로써 방문 처리를 해준다. 2. 토끼가 있던 다음 열부터 반복을 시작한다. 다음 열부터 하는 이유는 첫째, 토끼는 앞으로만 이동하기 때문이다. 두번쨰는 앞으로만 이동하기 때문에 뒤에 상황은 볼 필요가 없다. 세번째, 방향을 반대로 ↙,↖,← 이 3가지 방향으로 생각할 것이기 때문이다. 3. ..

★ 접근 적당히 큰 입력 값의 크기, 구해야 하는 모든 경우의 수들을 종합적으로 봤을 때 바로 다이나믹 프로그래밍을 떠올렸다. ★ 풀이 1. 비행을 할 때 한 지점에 도달할 수 있는 경우의 수는 이전 x좌표에서 아래에서 위로 올라온 것과 이전 x좌표에서 위에서 아래로 내려온 경우의 수를 합친 경우이다. 2. 1번이 전부이다.... 항상 dp가 그렇죠 뭐..... 점화식만 세우면 끝이니... 근데 이 정도로 간단할 줄은.... 그래도 골드4인데... 황당... - 코드 import sys input = sys.stdin.readline d,m = map(int,input().split()) dp = [[0] * 4001 for _ in range(4001)] dp[1][1] = 1 for i in rang..

★ 접근법 문제에서 우선순위가 높은 프로세스 기준 프로세스가 같다면 id가 작은 것이 우선이라고 했을 때 => 우선순위, 최대 십만크기 바로 heapq를 떠올렸다. ★ 풀이법 나머지 프로세스의 우선순위를 1 증가시키는 방법만 떠올린다면 말도 안되게 쉬운 문제이다. 그대로 구현하면 최대 백만 초 * 최대 십만 개의 프로세스이기 때문에 시간초과가 발생한다. 나머지 프로세스의 우선순위를 1 증가시키는 것이 아닌 자신의 프로세스를 1 감소시키는 것이다. 우선순위는 상대적이기 때문에 나의 우선순위를 1 감소시키면 자연스럽게 나머지 프로세스의 우선순위가 1 증가된 것처럼 보인다. - 코드 import sys,heapq input = sys.stdin.readline t,n = map(int,input().split..

● 접근법 d와n의 최대 길이는 300,000이다. 이중 반복문을 쓸 경우 무조건 시간 초과가 발생한다. 그렇다면 여기서 반복 한 번 만에 이 문제를 해결해야 한다는 것을 알 수 있다. ● 풀이법 1. 피자는 자신보다 지름이 작은 오븐 밑으로는 내려 갈 수 없다. 즉, 오븐은 내림차순 정렬(진짜로 sort(reverse = True) 하라는 뜻이 아니다.) 현재 오븐 칸 보다 바로 밑에 있는 칸의 지름이 더 크다면 현재 오븐 칸의 지름으로 밑에 있는 칸의 지름을 바꿔도 된다는 뜻이다. 2. 그 다음 피자를 집어넣을 때 위에서 집어넣으면 의미없는 반복들을 진행해야 하기 때문에 밑에서부터 넣어주면 반복 한번에 피자를 오븐에 넣을 수 있는 지에 대한 여부를 알 수 있게 된다. ● 코드 d,n = map(int..

● 접근법 - 입력에서 n의 최대 크기가 123,456인데 대략 최대 십이만 이라고 생각해보자. 시간 제한은 1초이고 파이썬으로 for문 여러개를 썼다가는 시간 초과가 발생할 것이 뻔하다. 그럼 어떻게 시간 안에 최소를 구해야 할까? 여기서 생각은 단순해진다. for문을 한 번만 써야한다. 그리고 여기서 어떻게 한 번에 minHP를 구해야 하지? 뒤에서 부터 가면 되지 않을 까라는 생각을 했지만 t가 2일 경우 공격력이 점차 증가해 몬스터를 빨리 물리치니 뒤에서부터 계산할 수 없다는 것을 깨닫는다. 그럼 남은 방법은 앞에서부터 출발하는 하나의 방법이 남는다. ● 풀이법 1. 누적된 데미지, 공격력을 위한 변수 td, ta를 만든다. 2. t가 1일 경우 td를 빼주고 매 반복마다 td의 최솟값을 갱신해준..

● 접근 방법 문제에서 상하좌우로 이동한다는 힌트를 줘서 bfs인 것을 알았고 격자의 크기가 50으로 크지 않았기 때문에 bfs로 풀기로 결정했다. ● 풀이법 문제에서 '다음 시간에 물이 찰 예정인 칸으로 고슴도치는 이동할 수 없다.' 이런 말을 한다. 이 말을 보고 물을 먼저 움직여야겠다고 생각했다. 왜냐하면 물과 고슴도치는 동시에 움직이는 것이지만 물을 먼저 움직여놓고 도치가 움직인다고 했을 때 그 칸에 물이 있으면 즉, 물이 이동할 예정인 칸이었으면 도치가 해당 칸으로는 이동하지 못하기 때문이다. 그러나 유의해야 할 점은 필자는 여기서 많이 헤맸는데 임의로 물을 먼저 움직인다고 가정했을 뿐이지 도치와 물은 동시에 움직이는 것이다. 즉, 물을 먼저 움직여 도치가 있는 칸에 물이 들어왔다고 하더라도 사..