문제 링크 https://www.acmicpc.net/problem/4181 4181번: Convex Hull 때때로 주어진 점들 사이에서 볼록 껍질(Convex Hull)을 찾아내는 기술은 요긴하게 쓰인다. ACM 월드파이널에서 볼록 껍질을 응용해야 하는 문제가 출제되다 보니, 이걸 할 줄 아는 것은 참가자의 소 www.acmicpc.net 문제 때때로 주어진 점들 사이에서 볼록 껍질(Convex Hull)을 찾아내는 기술은 요긴하게 쓰인다. ACM 월드파이널에서 볼록 껍질을 응용해야 하는 문제가 출제되다 보니, 이걸 할 줄 아는 것은 참가자의 소양이 되었다. 이 작업은 크게 두 단계의 과정으로 이루어진다. 첫 번째 단계는 볼록 껍질을 이루는 점들을 찾아내는 것이고, 두 번째 단계는 이 점들을 반시계 ..

문제 링크 https://www.acmicpc.net/problem/17394 17394번: 핑거 스냅 [어벤져스] 시리즈를 보지 않은 사람이라도 ‘인피니티 건틀렛’이 무엇인지는 다들 알 것이다. 그래도 모르는 사람들을 위해 설명을 하자면, 인피니티 스톤이 모두 모인 인피니티 건틀렛을 끼 www.acmicpc.net 문제 [어벤져스] 시리즈를 보지 않은 사람이라도 ‘인피니티 건틀렛’이 무엇인지는 다들 알 것이다. 그래도 모르는 사람들을 위해 설명을 하자면, 인피니티 스톤이 모두 모인 인피니티 건틀렛을 끼고 손가락을 튕기면, 사용자가 원하는 것을 할 수 있다. 그러나 반동이 매우 심하기 때문에 그리 많이는 사용할 수 없다. 정신 나간 수학자 Sonaht는 우연히 이 인피니티 건틀렛을 손에 넣게 된다. 그러..

문제 링크 https://www.acmicpc.net/problem/23048 23048번: 자연수 색칠하기 $1$부터 $N$까지의 자연수를 색칠한다. 단, 서로소인 서로 다른 두 자연수는 다른 색으로 칠해야 한다. 최소한의 색을 써서 모든 자연수를 칠하는 방법을 찾는 프로그램을 작성하자. www.acmicpc.net 문제 1부터 N까지의 자연수를 색칠한다. 단, 서로소인 서로 다른 두 자연수는 다른 색으로 칠해야 한다. 최소한의 색을 써서 모든 자연수를 칠하는 방법을 찾는 프로그램을 작성하자. 입력 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 500,000) 출력 첫째 줄에 사용한 색의 수 K를 출력한다. 둘째 줄에 N개의 수를 공백을 사이에 두고 출력한다. i번째 수는 자연수 i의 색이다. 색은..

문제 링크 https://www.acmicpc.net/problem/15961 15961번: 회전 초밥 첫 번째 줄에는 회전 초밥 벨트에 놓인 접시의 수 N, 초밥의 가짓수 d, 연속해서 먹는 접시의 수 k, 쿠폰 번호 c가 각각 하나의 빈 칸을 사이에 두고 주어진다. 단, 2 ≤ N ≤ 3,000,000, 2 ≤ d ≤ 3,000, 2 www.acmicpc.net 문제 회전 초밥 음식점에는 회전하는 벨트 위에 여러 가지 종류의 초밥이 접시에 담겨 놓여 있고, 손님은 이 중에서 자기가 좋아하는 초밥을 골라서 먹는다. 초밥의 종류를 번호로 표현할 때, 다음 그림은 회전 초밥 음식점의 벨트 상태의 예를 보여주고 있다. 벨트 위에는 같은 종류의 초밥이 둘 이상 있을 수 있다. 새로 문을 연 회전 초밥 음식점이..

문제 링크 https://www.acmicpc.net/problem/13422 13422번: 도둑 입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫째 줄에 테스트 케이스의 개수를 나타내는 자연수 T가 주어진다. 각각의 테스트 케이스의 첫째 줄에 마 www.acmicpc.net 문제 다음 그림과 같이 N개의 집이 순서대로 이웃하여 세워진 마을이 있다. 위 그림은 N = 8인 경우 마을의 모습이다. 위 그림과 같이 각각의 집은 순서대로 서로 이웃해 있으며, 첫 번째 집과 마지막 집 또한 이웃해 있다. 예를들면 3이 적힌 집은 9, 4가 적힌 집과 이웃해 있으며, 5가 적힌 집은 6, 7이 적힌 집과 이웃해 있다. 이 마을 사람들은 각자 자신의 집에 돈을 보관한다. 위 ..

문제 링크 https://www.acmicpc.net/problem/25603 25603번: 짱해커 이동식 첫 번째 줄에 정수 $N$, $K$가 주어진다. ($1 \le K < N \le 100\,000$) 두 번째 줄부터 $N$개의 기업 의뢰의 비용이 주어진다. 비용은 $1$ 이상 $10^9$ 이하의 정수이다. www.acmicpc.net 문제 짱해커 이동식은 상대방의 디스크에 자신의 이름을 남겨 자신이 왔다간 것을 알린다. 이동식에게 인정받기 위해 오늘도 수많은 기업들의 보안담당자들은 모의해킹 의뢰를 하기 위해 줄을 선다. 모든 의뢰를 받아들이기엔 너무 부담이 됐기 때문에, 각 의뢰들을 수행하는 데 필요한 비용을 측정해 최대한 비용이 적게 드는 의뢰들을 받으려 한다. 하지만, 의뢰를 연속으로 K번 이..

문제 링크 https://www.acmicpc.net/problem/27527 27527번: 배너 걸기 현대오토에버는 현대자동차그룹의 모빌리티 소프트웨어 전문 기업으로서, In-Car와 Out-Car 영역 전반의 소프트웨어와 인프라를 안정적, 효율적, 혁신적으로 지원하는 'Mobility SW Provider' 역할을 수 www.acmicpc.net 문제 현대오토에버는 현대자동차그룹의 모빌리티 소프트웨어 전문 기업으로서, In-Car와 Out-Car 영역 전반의 소프트웨어와 인프라를 안정적, 효율적, 혁신적으로 지원하는 'Mobility SW Provider' 역할을 수행하고 있다. 당신은 현대오토에버의 다양한 소프트웨어 기술을 선보이기 위한 행사를 준비하고 있으며, 행사는 현대오토에버 본사가 위치한 서..

문제 링크 https://www.acmicpc.net/problem/14217 14217번: 그래프 탐색 남규나라의 왕 zych는 도로 정비 계획을 발표하였다. 두 도시를 잇는 도로들을 새로 만들거나, 안전상의 문제로 도로를 없애기도 할 계획이다. 도로 정비 계획은 두 도시와, 만들건지, 없앨건지에 www.acmicpc.net 문제 남규나라의 왕 zych는 도로 정비 계획을 발표하였다. 두 도시를 잇는 도로들을 새로 만들거나, 안전상의 문제로 도로를 없애기도 할 계획이다. 도로 정비 계획은 두 도시와, 만들건지, 없앨건지에 대한 정보가 주어지는데, 도로를 정비하는 일은 매우 큰 일이기에 계획을 순서대로 하나씩 시행해 나갈 것이다. 상황에 따라서는 계획에 포함돼서 만들어진 도로를 제거할 수도 있다. Zyc..

문제 링크 https://www.acmicpc.net/problem/27737 27737번: 버섯 농장 첫 번째 줄에 $N$, $M$, $K$가 공백으로 구분되어 주어진다. 두 번째 줄부터 $N$개의 줄에 나무판의 각 칸의 상태가 공백으로 구분되어 주어진다. 버섯이 자랄 수 있는 칸은 0, 버섯이 자랄 수 없는 칸 www.acmicpc.net 문제 농부 해강이는 N × N 칸으로 이루어진 나무판에서 버섯 농사를 짓는다. 나무판은 버섯이 자랄 수 있는 칸과 없는 칸으로 이루어져 있다. 해강이는 M개의 버섯 포자를 가지고 있다. 버섯 포자는 버섯이 자랄 수 있는 칸에만 심을 수 있다. 각 버섯 포자는 포자가 심어진 칸을 포함해 최대 K개의 연결된 (버섯이 자랄 수 있는) 칸에 버섯을 자라게 한다. 이때 연결..

문제 링크 https://www.acmicpc.net/problem/23796 문제 호준이는 2048 게임을 발전시킨 2,147,483,648 게임을 하고 있다. 2,147,483,648 게임은 8×8 크기의 게임판에서 키보드의 방향키를 통해 2^k (1 ≤ k ≤ 30)꼴에 해당하는 정수가 쓰여 있는 타일들을 움직이며 2,147,483,648( = 2^31)을 만드는 것이 목적인 게임이다. 이 게임은 방향키가 눌렸을 때 다음과 같은 규칙으로 진행된다. 눌린 방향키와 같은 방향으로 타일들을 벽 끝까지 밀어 넣는다. 만약 밀어넣는 방향으로 같은 수가 두 타일 연속해서 존재한다면 그 두 타일을 합친다. 만약 세 타일 이상 연속해있다면 방향키가 가리키는 쪽의 벽에 가까운 쪽부터 두 개씩 합쳐진다. 한 번의 방..

문제 링크 https://www.acmicpc.net/problem/22234 22234번: 가희와 은행 가희는 창구가 하나인 은행을 운영하고 있습니다. 가희의 은행이 영업을 시작했을 때, 대기 줄에는 손님이 N명 있습니다. [그림 1] 카운터 직원과 N명의 손님 x번 손님에 대한 정보는 x번 손님의 www.acmicpc.net 문제 가희는 창구가 하나인 은행을 운영하고 있습니다. 가희의 은행이 영업을 시작했을 때, 대기 줄에는 손님이 N명 있습니다. [그림 1] 카운터 직원과 N명의 손님 x번 손님에 대한 정보는 x번 손님의 id 값인 Px와 업무를 처리하는 데 필요한 시간인 tx초로 정보가 주어지게 됩니다. 은행이 영업을 시작하고 난 후에 들어오는 손님은 M명 있습니다. 이 손님들은 입력을 받은 순서..

문제 링크 https://www.acmicpc.net/problem/14466 14466번: 소가 길을 건너간 이유 6 첫 줄에 N, K, R이 주어진다. 다음 R줄에는 한 줄에 하나씩 길이 주어진다. 길은 상하좌우로 인접한 두 목초지를 잇고, r c r′ c′의 형태 (행, 열, 행, 열)로 주어진다. 각 수는 1 이상 N 이하이다. www.acmicpc.net 문제 소가 길을 건너간 이유는 그냥 길이 많아서이다. 존의 농장에는 길이 너무 많아서, 길을 건너지 않고서는 별로 돌아다닐 수가 없다. 존의 농장에 대대적인 개편이 있었다. 이제 작은 정사각형 목초지가 N×N (2 ≤ N ≤ 100) 격자로 이루어져 있다. 인접한 목초지 사이는 일반적으로 자유롭게 건너갈 수 있지만, 그 중 일부는 길을 건너야 ..

문제 링크 https://www.acmicpc.net/problem/27211 27211번: 도넛 행성 준겸이는 $N \times M$칸으로 이루어진 도넛 모양의 행성에 살고 있다. 준겸이가 살고 있는 행성에는 위 그림처럼 격자 모양으로 줄이 그어져 있다. 행성의 각 칸은 숲으로 막혀 있거나, 지나갈 수 www.acmicpc.net 문제 준겸이는 N × M칸으로 이루어진 도넛 모양의 행성에 살고 있다. 준겸이가 살고 있는 행성에는 위 그림처럼 격자 모양으로 줄이 그어져 있다. 행성의 각 칸은 숲으로 막혀 있거나, 지나갈 수 있도록 비어 있다. 준겸이는 본인의 집이 있는 위치를 기준으로 삼아 (0, 0)이라고 표시하기로 했다. 준겸이는 행성 위에서 상하좌우로 걸어 다닐 수 있다. 준겸이가 오른쪽으로 한 칸..

문제 링크 https://www.acmicpc.net/problem/17234 17234번: Scoring Hack n, a, b 세 개의 정수가 띄어쓰기를 사이에 두고 주어진다. (1 ≤ n ≤ 500, 1 ≤ b ≤ a ≤ 100) www.acmicpc.net 문제 0점에서 시작해 매 턴 점수를 획득해 나가는 게임이 있다. 각 턴에서 플레이어가 게임 에서 승리하면 a점을 얻고, 지면 b점을 얻는다. 점수의 총합이 n점 이상이면 게임이 끝나게 된다. 포스텍의 한 학생이 이 게임을 해킹하는 데 성공했다. 그래서 각 턴에서 승리할지, 질지 자유롭게 결정할 수 있다. 심지어는 원하는 턴에서 점수를 a점이나 b점 올리는 대신 두 배로 바꾸는 것도 가능하다. 예를 들면 a가 3이고 b가 2이며 현재 점수가 10..

문제 링크 https://www.acmicpc.net/problem/26009 26009번: 험난한 등굣길 통학러 재헌이는 1교시 수업을 듣기 위해 아침 일찍 학교에 가려고 한다. 재헌이가 사는 지역은 크기가 $N \times M$ 인 격자로 나타낼 수 있는데, $i$행 $j$열에 해당하는 칸을 $(i, j)$로 나타낼 때 재 www.acmicpc.net 문제 통학러 재헌이는 1교시 수업을 듣기 위해 아침 일찍 학교에 가려고 한다. 재헌이가 사는 지역은 크기가 N × M인 격자로 나타낼 수 있는데, i행 j열에 해당하는 칸을 (i, j)로 나타낼 때 재헌이는 현재 (1, 1)에, 학교는 (N, M)에 위치해 있다. 재헌이는 상하좌우로 한 칸씩 이동할 수 있고 지역 바깥으로 나갈 수는 없다. 등굣길은 순탄..