STUDY

역사 문제 역사, 그 중에서도 한국사에 해박한 세준이는 많은 역사적 사건들의 전후 관계를 잘 알고 있다. 즉, 임진왜란이 병자호란보다 먼저 일어났으며, 무오사화가 기묘사화보다 먼저 일어났다는 등의 지식을 알고 있는 것이다. 세준이가 알고 있는 일부 사건들의 전후 관계들이 주어질 때, 주어진 사건들의 전후 관계도 알 수 있을까? 이를 해결하는 프로그램을 작성해 보도록 하자. 입력 첫째 줄에 첫 줄에 사건의 개수 n(400 이하의 자연수)과 알고 있는 사건의 전후 관계의 개수 k(50,000 이하의 자연수)가 주어진다. 다음 k줄에는 전후 관계를 알고 있는 두 사건의 번호가 주어진다. 이는 앞에 있는 번호의 사건이 뒤에 있는 번호의 사건보다 먼저 일어났음을 의미한다. 물론 사건의 전후 관계가 모순인 경우는 ..

나만 안되는 연애 문제 깽미는 24살 모태솔로이다. 깽미는 대마법사가 될 순 없다며 자신의 프로그래밍 능력을 이용하여 미팅 어플리케이션을 만들기로 결심했다. 미팅 앱은 대학생을 타겟으로 만들어졌으며 대학교간의 도로 데이터를 수집하여 만들었다. 이 앱은 사용자들을 위해 사심 경로를 제공한다. 이 경로는 3가지 특징을 가지고 있다. 사심 경로는 사용자들의 사심을 만족시키기 위해 남초 대학교와 여초 대학교들을 연결하는 도로로만 이루어져 있다. 사용자들이 다양한 사람과 미팅할 수 있도록 어떤 대학교에서든 모든 대학교로 이동이 가능한 경로이다. 시간을 낭비하지 않고 미팅할 수 있도록 이 경로의 길이는 최단 거리가 되어야 한다. 만약 도로 데이터가 만약 왼쪽의 그림과 같다면, 오른쪽 그림의 보라색 선과 같이 경로를..

버스 노선 개편하기 문제 서강 나라에서는 일직선 도로를 따라 $N$개의 버스 노선을 운영 중이다. 필요할 때마다 노선을 새로 만든 탓에 겹치거나 중복되는 노선이 많다. 복잡한 버스 노선에 지친 시민들을 위해 버스 노선을 개편하기로 했다. 각 버스 노선은 세 정수 $S$, $E$, $C$로 나타낼 수 있으며, 구간 $[S,E]$를 요금 $C$로 운행한다는 뜻이다. 어떤 두 버스 노선의 구간이 한 점 이상에서 겹친다면, 두 구간을 합친 새 노선으로 대체한다. 이때 요금은 더 낮은 금액의 요금을 따르기로 했다. 버스 노선 개편은 구간이 겹치는 버스 노선이 없을 때까지 진행한다. 그림 D.1: 개편 전과 개편 후의 버스 노선도 버스 노선들의 정보가 주어지면, 개편이 끝난 후 버스 노선의 정보를 출력하는 프로그램..

레이저빔은 어디로 문제 레이저박스라는 게임은 정사각형 모양의 n x n 보드에서 진행한다. (체스판을 상상하면 된다) 레이저박스의 임의의 칸마다 우향우 거울이라는 장치가 설치되어 있고, 마지막으로 레이저 한개가 설치되어 있다. 레이저는 판의 끝에만 설치 될 수 있는데, 행의 맨 아래/맨 위, 열의 오른쪽 끝/왼쪽 끝에 설치 될 수 있다. 레이저에서 나온 빔은 그 행 혹은 열을 질러서 반대쪽을 비춘다. 게임은 우향우 거울을 임의의 칸마다 설치한 후, 레이저를 배치를 해 놓은 이후에 시작한다. 레이저를 켰을 때 나온 빔이 우향우 거울을 통과하면 진입한 방향과는 관계 없이 오른쪽으로 90도를 꺾어 다시 나아간다. 레이저 빔이 마지막으로 어느 좌표를 향해 비춰지는지 구하라. 입력 첫 줄에는 테스트케이스의 총 개..

치킨 배달 문제 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸, 왼쪽에서부터 c번째 칸을 의미한다. r과 c는 1부터 시작한다. 이 도시에 사는 사람들은 치킨을 매우 좋아한다. 따라서, 사람들은 "치킨 거리"라는 말을 주로 사용한다. 치킨 거리는 집과 가장 가까운 치킨집 사이의 거리이다. 즉, 치킨 거리는 집을 기준으로 정해지며, 각각의 집은 치킨 거리를 가지고 있다. 도시의 치킨 거리는 모든 집의 치킨 거리의 합이다. 임의의 두 칸 (r1, c1)과 (r2, c2) 사이의 거리는 |r1-r2| + |c1-c2|로 구한다. 예를 들어, 아래..

경로 게임 문제 현정이는 경로 게임을 하고 있다. 경로 게임은 정사각형 칸으로 이루어져 있는 직사각형 격자판에서 진행된다. 격자판의 행의 개수는 항상 2이며, 열의 개수는 양수이다. 각 칸은 검정색 또는 하얀색으로 칠해져 있다. 격자에서 왼쪽-오른쪽 경로는 시작 칸이 가장 왼쪽 열에 있는 칸이고, 마지막 칸이 가장 오른쪽 열에 있는 경로이다. 이때, 경로 상의 모든 칸은 하얀색이어야 하며, 경로상에서 연속하는 칸은 모두 인접해야 한다. 격자판의 하얀색 칸을 검정색 칸으로 바꾼 경우에도 왼쪽-오른쪽 경로가 존재할 수도 있다. 이때, 왼쪽-오른족 경로가 존재하면서 바꿀 수 있는 하얀색 칸의 최댓값을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 열의 개수 M이 주어진다. (M ≤ 50) 둘째 줄부터 두 개의..

도서관 문제 세준이는 도서관에서 일한다. 도서관의 개방시간이 끝나서 세준이는 사람들이 마구 놓은 책을 다시 가져다 놓아야 한다. 세준이는 현재 0에 있고, 사람들이 마구 놓은 책도 전부 0에 있다. 각 책들의 원래 위치가 주어질 때, 책을 모두 제자리에 놔둘 때 드는 최소 걸음 수를 계산하는 프로그램을 작성하시오. 세준이는 한 걸음에 좌표 1칸씩 가며, 책의 원래 위치는 정수 좌표이다. 책을 모두 제자리에 놔둔 후에는 다시 0으로 돌아올 필요는 없다. 그리고 세준이는 한 번에 최대 M 권의 책을 들 수 있다. 입력 첫째 줄에 책의 개수 N 과, 세준이가 한 번에 들 수 있는 책의 개수 M 이 주어진다. 둘째 줄에는 책의 위치가 주어진다. N 과 M 은 50보다 작거나 같은 자연수이다. 책의 위치는 0이 ..

IPv6 문제 IPv6은 길이가 128비트인 차세대 인터넷 프로토콜이다. IPv6의 주소는 32자리의 16진수를 4자리씩 끊어 나타낸다. 이때, 각 그룹은 콜론 (:)으로 구분해서 나타낸다. 예를 들면, 다음과 같다. 2001:0db8:85a3:0000:0000:8a2e:0370:7334 32자리의 16진수는 사람이 읽고 쓰기에 불편하고, 대부분의 자리가 0이기 때문에 아래와 같이 축약할 수 있다. 각 그룹의 앞자리의 0의 전체 또는 일부를 생략 할 수 있다. 위의 IPv6을 축약하면, 다음과 같다. 2001:db8:85a3:0:00:8a2e:370:7334 만약 0으로만 이루어져 있는 그룹이 있을 경우 그 중 한 개 이상 연속된 그룹을 하나 골라 콜론 2개(::)로 바꿀 수 있다. 2001:db8:85..

돌 게임 6 문제 돌 게임은 두 명이서 즐기는 재밌는 게임이다. 탁자 위에 돌 N개가 있다. 상근이와 창영이는 턴을 번갈아가면서 돌을 가져가며, 돌은 1개, 3개 또는 4개 가져갈 수 있다. 마지막 돌을 가져가는 사람이 게임을 이기게 된다. 두 사람이 완벽하게 게임을 했을 때, 이기는 사람을 구하는 프로그램을 작성하시오. 게임은 상근이가 먼저 시작한다. 입력 첫째 줄에 N이 주어진다. (1 ≤ N ≤ 1,000,000,000,000) 출력 상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY을 출력한다. 게임 이론 문제 였긴 때문에 규칙을 찾기로 하였다. 그래서 1, 3, 4개를 선택할 수 있기 때문에 4 까지는 구해보았다. 그랬을 때 SK, CY, SK, SK 가 나왔다 그래서 N=5일 때는 N..

나이트 게임 문제 나이트 게임은 크기가 N×N인 체스판 위에서 진행되는 게임이고, 나이트를 하나씩 턴을 번갈아가며 놓는 게임이다. 나이트는 이미 놓여져 있는 나이트가 공격할 수 있는 칸에 놓을 수 없다. 나이트를 (r, c)에 놓은 경우에는 (r-2, c+1), (r-1, c+2), (r+1, c+2), (r+2, c+1), (r+2, c-1), (r+1, c-2), (r-1, c-2), (r-2, c-1)이 공격할 수 있는 칸이다. 나이트를 놓을 수 있는 칸이 없는 사람이 게임을 지게 된다. 구사과와 큐브러버가 이 게임을 최적의 방법으로 플레이했을 때, 이기는 사람을 구하는 프로그램을 작성하시오. 게임은 구사과가 먼저 시작한다. 입력 첫째 줄에 테스트 케이스의 개수 T(1 ≤ T ≤ 100)가 주어진다..