문제https://www.acmicpc.net/problem/2157문제 설명1번부터 N번까지 도시가 존재한다.이 중 M개 이하의 도시를 여행해야 한다.여행 경로는 반드시 1번 도시에서 시작해서 N번 도시에서 끝내야한다.1번과 N번 도시도 M개의 도시에 포함된다.무조건 번호가 증가하는 도시로만 이동이 가능하다.먹게 되는 기내식의 점수의 총 합의 최댓값을 구한다.풀이처음에는 DFS로 접근했지만, 나올 수 있는 경우의 수가 300!(N은 최대 300)이기 때문에 시간초과가 발생했다.그래서 다이나믹 프로그래밍을 통해 문제를 풀이했다. 이 문제의 핵심은 바로 M에 존재한다. 1과 2 노드에서 각각 3으로 이동하고 M = 3이라고 가정하자.1 -> 3일 때 도시를 지난 횟수는 3개이고, cost = 10이다.2 ..

문제https://www.acmicpc.net/problem/20057문제 설명마법사 상어는 N*N 크기의 모래밭에서 토네이도 마법을 연습한다.각 (r,c)의 값은 모래의 양을 의미한다.격자의 중앙부터 토네이도가 시작된다.(예시는 그림으로 대체)토네이도 위치가 x일 때 y에 있는 모래가 각 비율, a위치로 뿌려지게 된다.a위치의 모래는 비율로 뿌린 모래의 나머지다.토네이도가 (0,0)으로 이동하게 되면, 소멸된다.토네이도가 소멸되었을 때, 격자 밖으로 나간 모래의 양을 구한다풀이마법사 상어 기출 문제들 중 가장 쉽게 풀린 문제이다.단순히 네 방향으로 이동할 때 흩뿌려지는 좌표를 하나하나 계산해서 모래를 넣어주기만 하면 된다.방향을 정의하고 왼쪽부터 토네이도를 시작한다.방향에 따라 모래를 흩뿌린다.이 때 ..

문제https://www.acmicpc.net/problem/20056문제 설명마법사 상어는 N*N 격자에 파이어볼 M개를 발사한다.각 파이어볼의 위치는 (r,c), 질량은 m, 방향은 d, 속력은 s 이다. 1번 행은 N번과 연결되어 있고, 1번 열은 N번 열과 연결되어 있다.마법사 상어가 파이어 볼에게 명령을 내린다. 모든 파이어볼이 자신의 방향 d로 속력 s칸 만큼 이동한다.이 때 같은 위치에 여러 개의 파이어볼이 이동할 수 있다.이동이 끝난 후같은 칸에 있는 파이어볼은 모두 하나로 합쳐진 후 나뉘어진다.질량은 ⌊ 합쳐진 파이어볼 질량의 합 / 5 ⌋ 이다.속력은⌊ (합쳐진 파이어볼 속력의 합 / 합쳐진 파이어볼의 개수)⌋ 이다.합쳐지는 파이어볼의 방향이 모두 홀수이거나 짝수이면, [0,2,4,6]..

문제https://www.acmicpc.net/problem/17086문제 설명N*M 크기의 공간에 아기 상어 여러 마리가 있다.안전거리는 현재 칸에서 아기 상어와 가장 가까운 거리를 말한다.인접한 8방향으로 이동이 가능하다.이 때 모든 칸을 기준으로 안전거리의 최댓값을 구한다. 풀이단순 BFS 문제이다. 매 위치를 갱신하면서 다음 위치가 현재 위치 + 1 거리보다 크다면 갱신하도록 탐색했다.배열을 완전 탐색하여 상어의 위치를 전부 queue에 넣는다.BFS을 진행한다.만약 현재 위치 (y,x)에서 1을 더한 크기가 (ny,nx)의 안전거리보다 더 작다면 갱신한다.max_dist를 통해 갱신될 때 마다 최댓값을 갱신한다.결과를 출력한다. 코드import sysfrom collections import ..

문제https://www.acmicpc.net/problem/19237문제 설명N*N 크기의 격자에 M마리의 상어가 존재한다.상어들은 자신들의 위치를 냄새를 뿌리고 시작한다.상어들은 한 번에 여러 행동들을 수행한다.모든 상어가 우선순위에 맞게 동시에 상하좌우로 이동한다.인접한 칸 중 아무 냄새가 없는 칸의 방향으로 이동한다.냄새가 전부 있다면, 자신의 냄새가 있는 칸의 방향으로 이동한다.이 때 가능한 칸이 여러개라면 입력으로 주어진 우선순위에 맞게 이동한다.*참고로 상어가 이동할 수 없는 경우는 존재하지 않는다.이동 후 현재 위치에 자신의 냄새를 뿌린다.냄새는 K번 이동 후 사라진다.이동을 마쳤을 때 같은 위치에 여러 마리의 상어가 존재하면, 번호가 낮은 상어를 제외하고 전부 쫒겨난다.풀이상어 문제 중에..

문제https://www.acmicpc.net/problem/12764문제 설명N명의 사람이 주어진다.각 사용자의 컴퓨터 이용 시작 시각 P와 종료 시각 Q가 주어진다. 컴퓨터 자리는 1번부터 순서대로 번호가 매겨져 있으며, 비어있는 자리 중 번호가 가장 작은 자리에 앉아야 한다.모든 사람이 기다리지 않고 이용할 수 있는 컴퓨터의 최소 개수와 몇 명의 사람이 사용했는가를 구한다. 풀이아직 싸지방에 들어가지 않은 사람들을 hq에 저장한다.이용시간이 가장 빠른 사람 먼저 힙에서 꺼낸다.다음에 이용할 사람을 hq에서 꺼낸 후 어느 자리에 들어갈 수 있는지 검증한다.이용중인 사람을 저장한 hq2에서 종료시간이 가장 빠른 사람을 꺼낸다.다음 사람이 들어왔을 시점에 이미 사용이 종료한 사람이라면 hq2에서 전부 꺼..

문제https://www.acmicpc.net/problem/2637문제 설명 여러 가지 부품을 조립하여 장난감을 만든다.기본 부품은 재료가 필요 없다.중간 부품은 기본 부품들을 이용해서 만든다.완제품은 중간 부품 혹은 기본 부품을 사용해 만든다.N이 주어지면 1부터 N-1번째까지는 기본 부품 혹은 중간 부품, N은 완제품의 번호를 나타낸다.완제품을 만들려면 기본 부품이 총 몇 개 필요한지 출력한다.풀이문제를 처음 봤을 때 가장 높은 노드 즉, 완제품부터 순차적으로 너비 탐색을 진행하면 최종적으로 기본 부품들의 개수를 구할 수 있을 것이라 생각했다. 하지만 BFS로는 풀리지 않았다. 왜냐하면 높은 번호의 중간 부품이 하위 부품을 갱신한 상태에서, 나중에 그 하위 부품을 재 갱신할 때 값이 일치하지 않는..

문제https://www.acmicpc.net/problem/19644문제 설명킬로와 헥토에게 좀비가 1m씩 다가온다.좀비가 1m 다가올 때 마다 기관총 혹은 수평 세열 지향성 지뢰 중 1개를 선택하여 좀비를 공격할 수 있다.기관총: Ml만큼의 사거리에 있는 모든 좀비에게 Mk 데미지만큼 공격할 수 있다.수평 세열 지향성 지뢰: 1m에 있는 좀비를 즉사시킨다.좀비가 킬로와 헥토에게 도착하게 되면 둘은 죽게된다.좀비가 계속해서 다가올 때 최종적으로 킬로와 헥토가 살아남을 수 있는지 판단한다. 풀이처음에는 단순하게 1m씩 다가오면서 완전 탐색을 진행해 보았지만, 시간초과가 발생했다.최대 $L = 3*10^6, Ml = 3*10^6$이기 때문에 매 순간 L위치에서 Ml만큼 반복을 하게되면 약 $L*Ml = ..

문제https://www.acmicpc.net/problem/3018문제 설명N명의 캠프파이어 참가자가 주어진다.E회 만큼 캠프파이어가 진행된다.선영이가 캠프파이어를 참가한다면 새로운 노래를 만들고, 다른 사람들은 새로운 노래만 배운다.선영이가 캠프파이어를 참가하지 않는다면, 사람들은 서로 아는 노래를 모두 공유한다.모든 캠프파이어가 진행된 후 선영이가 알고 있는 노래를 전부 아는 사람들을 오름차순으로 출력한다. 풀이선영이가 참가할 때는 참가자들에게 새로 생긴 노래만 추가한다.선영이가 참가하지 않을 때는 참가자들끼리 서로 노래를 공유해야 한다. 따라서 캠프파이어 각 참가자의 노래를 합집합하여 노래를 통합한다. 참가자들이 알고 있는 노래를 저장할 people 배열을 생성한다.매 캠프파이어 마다 선영이가..

문제https://www.acmicpc.net/problem/32979문제 설명아파트 게임을 T회 진행한다.교선이가 정수 b를 부른다.참가자들은 아래에서부터 B번까지 수를 세며, 아래에서 손을 위로 옮긴다.B번째 수를 셀 때 맨 아래에 있는 손의 참가자가 게임을 패배한다.현재 게임이 끝난 상태로 다음 게임을 진행한다.여러 게임을 진행했을 때 패배자들을 한 줄로 출력한다. 풀이참가자들의 손 구조를 queue에 입력한다.B회만큼 queue를 작동한 후 패배자를 출력한다.코드import sysfrom collections import dequeinput = sys.stdin.readlineN = int(input())T = int(input())queue = deque(list(map(int,input()...