조준장 개발자 생존기

문제 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 알고리즘 - 백 트래킹과 bfs 탐색을 한 번에 수행한다. - 벽을 3개 세울 때까지 백 트래킹 후 3개 세웠다면 바이러스 위치에서 bfs 탐색을 한다. - 탐색 후 안전한 위치를 카운트하여 최댓값을 출력한다. 코드 pypy3 통과 import sys from collections import deque import copy # 백 트래킹 def back_tracking(cnt): global answer # 벽을 3개 세웠다면 if cnt == 3: answer = m..

문제 10989번: 수 정렬하기 3 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. www.acmicpc.net 알고리즘 - 반복문을 통해 dp[idx] 위치에 수를 카운트한다. - 10001번 반복해서 받은 수에 개수를 출력한다. 코드 import sys n = int(sys.stdin.readline()) dp = [0] * 10001 # 반복문을 통해 dp[idx] 위치에 수를 카운트한다. for _ in range(n): dp[int(sys.stdin.readline())] += 1 # 10001번 반복해서 받은 수에 개수를 출력한다. for i in range(1, 10001):..

문제 11060번: 점프 점프 재환이가 1×N 크기의 미로에 갇혀있다. 미로는 1×1 크기의 칸으로 이루어져 있고, 각 칸에는 정수가 하나 쓰여 있다. i번째 칸에 쓰여 있는 수를 Ai라고 했을 때, 재환이는 Ai이하만큼 오른쪽으로 www.acmicpc.net 알고리즘 - 반복문을 통해 점프를 확인한다. - 점프로 갈 수 있는 칸을 확인하여 점프한 칸에 점프 횟수에 값을 최솟값으로 초기화한다. - 마지막 칸에 점프 횟수가 바뀌었다면 점프 횟수를 출력하고 아니라면 -1을 출력한다. 코드 # 10:25 => 10:51 import sys n = int(sys.stdin.readline()) a = list(map(int, sys.stdin.readline().split())) dp = [sys.maxsize..

문제 15988번: 1, 2, 3 더하기 3 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net 알고리즘 - dp를 통해 문제를 수행한다. - 규칙을 찾아보면 4부터 dp[n] = dp[n-3]+dp[n-2]+dp[n-1] 이라는 점화식을 구할 수 있다. - 1000001가지의 dp 값을 구하고 문제에 원하는 위치에 값을 출력한다. 코드 import sys t = int(sys.stdin.readline()) n = [int(sys.stdin.readline()) for _ in range(t)] dp = [0] * 1000001 dp[1] = 1 dp[2] = 2 dp[3] = 4 for i in ra..

문제 10819번: 차이를 최대로 첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다. www.acmicpc.net 알고리즘 - 백 트래킹을 통해 문제를 수행한다. - idx를 temp에 저장하고 삭제하는 것을 백트래킹 한다. - temp에 저장된 idx가 n 개라면 조건에 맞게 수를 더하고 answer에 저장한다. - answer의 최댓값을 출력한다. 코드 import sys def back_tracking(x): # x가 n개라면 => x == len(temp) # 조건에 맞게 수를 더해준다. if x == n: answer.append(sum(abs(m[temp[i + 1]] - ..

문제 18428번: 감시 피하기 NxN 크기의 복도가 있다. 복도는 1x1 크기의 칸으로 나누어지며, 특정한 위치에는 선생님, 학생, 혹은 장애물이 위치할 수 있다. 현재 몇 명의 학생들은 수업시간에 몰래 복도로 빠져나왔는데, 복 www.acmicpc.net 알고리즘 - 백트래킹을 통해 모든 위치를 탐색한다. - 3개의 장애물을 설치했다면 선생님의 위치에서 bfs 탐색을 하여 감시가 가능한 곳에 학생이 있는지 확인한다. - 3개의 장애물 설치 과정은 다음과 같다. - 모든 빈 공간에 장애물을 3개 설치한다. - 장애물을 설치한 곳에 "X"를 "O"로 초기화한다. - 장애물이 3개 설치한 후 탐색이 끝나면 백트래킹을 통해 "O"를 "X"로 초기화한 후 다음 위치에 장애물을 설치한다. 코드 import sy..

문제 19539번: 사과나무 첫 번째 줄에 모든 나무가 갊자가 바라는 높이가 되도록 물뿌리개를 통해 만들 수 있으면 “YES”를, 아니면 “NO”를 따옴표를 제외하고 출력한다. www.acmicpc.net 알고리즘 - 모든 나무의 합을 3으로 나누었을 때 0이 되지 않으면 물 뿌리개를 통해 만들 수 없는 나무의 높이인 것이다. - 반복문을 통해 2의 물 뿌리개의 횟수를 구한다. - 2의 물 뿌리개 횟수가 3으로 물을 뿌린 횟수보다 크다면 원하는 높이의 나무를 만들 수 있다. - 1의 물 뿌리개 횟수는 이미 이전에 3으로 나누어진 나무들이기 때문에 자동으로 뿌려진다. 코드 import sys n = int(sys.stdin.readline()) h = list(map(int, sys.stdin.readli..

문제 16198번: 에너지 모으기 N개의 에너지 구슬이 일렬로 놓여져 있고, 에너지 구슬을 이용해서 에너지를 모으려고 한다. i번째 에너지 구슬의 무게는 Wi이고, 에너지를 모으는 방법은 다음과 같으며, 반복해서 사용할 수 있 www.acmicpc.net 알고리즘 - 백트래킹을 통해 문제를 수행한다. - 에너지 구슬이 2개일 때까지 재귀적으로 탐색을 한다. - 에너지 구슬이 2개가 되면 그때의 최대 에너지 값으로 초기화한다. - 에너지 구슬이 2개가 아니라면 반복문을 통해 에너지 구슬을 확인한다. 여기서부터 백트래킹 부분 - i번째 구슬을 제거했을 때 나오는 에너지를 가지고 재귀적으로 탐색 - 재귀적인 탐색이 끝났다면 제거한 에너지 구슬을 추가하고 다시 반복한다. - 재귀적으로 탐색하는 과정에서 에너지를..

문제 13335번: 트럭 입력 데이터는 표준입력을 사용한다. 입력은 두 줄로 이루어진다. 입력의 첫 번째 줄에는 세 개의 정수 n (1 ≤ n ≤ 1,000) , w (1 ≤ w ≤ 100) and L (10 ≤ L ≤ 1,000)이 주어지는데, n은 다리를 건너는 트 www.acmicpc.net 알고리즘 - 반복문을 통해 다리의 모든 트럭이 지나갈 때까지 반복한다. - 모든 트럭을 확인하고 현재 다리에 있는 트럭과 다리를 건너려는 트럭의 무게가 다리의 하중보다 크다면 빈 공간을 추가한다. - 반대로 다리의 하중보다 작다면 트럭을 다리에 추가한다. - 위 방법을 반복하면 모든 트럭이 다 지나가고 다리의 칸이 0이 되어 반복이 멈춘다. - 이때 카운트를 출력한다. 코드 import sys n, w, l =..

문제 17615번: 볼 모으기 첫 번째 줄에는 볼의 총 개수 N이 주어진다. (1 ≤ N ≤ 500,000) 다음 줄에는 볼의 색깔을 나타내는 문자 R(빨간색 볼) 또는 B(파란색 볼)가 공백 없이 주어진다. 문자열에는 R 또는 B 중 한 종류만 주 www.acmicpc.net 알고리즘 - 레드와 블루가 오른쪽과 왼쪽으로 모으는 경우를 생각해서 문제를 수행한다. - 모을 때 뭉텅이가 생기는 경우는 이사 온 볼을 제외한 그다음 볼만으로 모으면 된다. => 그다음 볼들이 있다면 그다음 볼들이 먼저 이동한 후에 첫 번째 볼이 이동하는 것이 최소 횟수이므로. 코드 import sys n = int(sys.stdin.readline()) m = list(map(str, sys.stdin.readline().str..