문제 이해 단계 https://www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net NxN짜리 격자판이 존재한다. 그리고 중간에 벽(1)이 존재한다. 그리고 2칸을 차지하는 파이프가 존재하는데, 무조건 (1,1)과 (1,2)에서 시작한다. 목표는 파이프가 벽에 부딪히지 않고, (N, N)까지 이동하는 것이다. 파이프는 회전이 가능한데, 움직이면서 회전이 가능하다. 회전은 한 번에 45도씩만 가능하다. 움직이는 방향은 →↓↘으로만 움직일 수..

문제 이해 단계 https://www.acmicpc.net/problem/19539 19539번: 사과나무 첫 번째 줄에 모든 나무가 갊자가 바라는 높이가 되도록 물뿌리개를 통해 만들 수 있으면 “YES”를, 아니면 “NO”를 따옴표를 제외하고 출력한다. www.acmicpc.net 일렬로 1부터 N번까지 나무가 존재하는데, 나무의 초기 높이는 모두 0이다. 그리고 나무를 1 성장시킬 수 있는 물뿌리개와, 나무를 2 성장시킬 수 있는 물뿌리개 2개가 존재한다. 두 물뿌리개는 무조건 동시에 뿌려야 하고, 한 나무에 몰아서 줘서 3을 성장시킬 수 있다. N개의 정수가 주어졌을 때, 해당 물뿌리개들로 해당 높이 배치를 만들 수 있는지 판단하는 문제 문제 접근 단계 문제의 조건부터 살펴보자. 나무의 개수는 최대..

문제 이해 단계 https://www.acmicpc.net/problem/11657 11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. www.acmicpc.net N개의 도시와 M개의 버스 노선이 주어진다. M개의 버스 정보로는 A, B, C가 들어오는데, (출발지, 도착지, 걸리는 시간)이다. 걸리는 시간에는 음수도 존재한다. 1번 도시에서 출발해서 각 도시별로 가장 빠른 시간을 출력한다. 이때, 무한대로 음수로 가는 시간이 나올 경우 -1을 출력한다. 또한 그 도시로 갈 수 없..

문제 이해 단계 입력으로 사원의 정보가 주어지는데 각각 (근무 태도 점수, 동료 평가 점수)로 이루어져 있다. 목표는 사원의 등수를 정하는 것이다. 이 중에서 다른 사원과 비교했을 때, 한 번이라도 다른 사원보다 두 점수가 둘 다 낮은 사원은 등수에서 제외한다. 그리고 등수는 점수가 높은 순으로 선정한다. 동점자가 존재하면 그 사원은 같은 등수이고, 그 뒤에 등수 하나가 없어진 등수가 다음 사원에게 간다. 해당 조건에서 가장 처음에 들어온 입력(인덱스 0) 사원의 등수를 구하는 문제 제외됐다면 -1을 출력 문제 접근 단계 문제의 제한 사항부터 살펴보자. scores의 길이, 그러니까 사원의 최대 수와 점수의 최댓값은 100,000이다. 여기서 더하는 행위는 근무 태도 + 동료 평가 밖에 없기 때문에 In..

문제 이해 단계 https://www.acmicpc.net/problem/16938 16938번: 캠프 준비 난이도가 10, 30인 문제를 고르거나, 20, 30인 문제를 고르면 된다. www.acmicpc.net N개의 문제가 나열되어 있고, 각 문제는 정수로 난이도가 표현되어 있다. 이 중에서 2문제 이상을 골라야 한다. 고른 문제 난이도의 합이 L 이상, R 이하가 되어야 하고 최댓값과 최솟값의 차이가 X 이상이어야 한다. 해당 조건을 만족하는 문제의 경우의 수는 총 몇 개인지를 고르는 문제 문제 접근 단계 문제의 조건부터 살펴보자. 문제의 개수 N이 최대 15개밖에 안된다. 이 말은 탐색할게 몇 개 없어서 완전 탐색을 해도 된다는 소리다. 그리고 L과 R은 최대 10^9이라 int 자료형을 넘을 ..

문제 이해 단계 https://www.acmicpc.net/problem/11509 11509번: 풍선 맞추기 첫 번째 예제 에서 [5,4,3] 을 터트리고 [2,1]을 터트리면 모든 풍선을 터트릴 수 있으므로 최소한 2개의 화살을 필요로 한다. www.acmicpc.net 왼쪽부터 오른쪽으로 일렬로 서있는 N개의 풍선이 있다. 그리고 화살은 H의 높이에서 오른쪽으로 출발하고 풍선에 부딪힐 때마다 풍선은 터지며, 화살은 높이가 H-1이 된다. 풍선과 화살은 높이가 같아야 부딪히는 것으로 간주한다. 해당 조건에서 N개의 풍선을 모두 터트릴 때, 가장 적은 화살을 사용해라. 그리고 그 화살의 개수를 출력해라 문제 접근 단계 문제의 조건부터 살펴보면, 풍선의 개수 N와 높이 H는 최대 1,000,000개이다...

문제 이해 단계 https://www.acmicpc.net/problem/16472 16472번: 고냥이 고양이는 너무 귀엽다. 사람들은 고양이를 너무 귀여워했고, 결국 고양이와 더욱 가까워지고 싶어 고양이와의 소통을 위한 고양이 말 번역기를 발명하기로 했다. 이 번역기는 사람의 언어를 고 www.acmicpc.net 소문자로 이루어진 알파벳 문자열이 주어진다. 또한 입력으로 N이 주어지는데, 서로 다른 종류의 알파벳을 인식할 수 있는 개수이다. 구해야 하는 것은 N개의 서로 다른 종류의 알파벳을 인식할 수 있을 때, 주어진 문자열에서 인식할 수 있는 연속된 문자열 중 최대 길이를 구하는 문제 문제 접근 단계 늘 그렇듯, 제한사항부터 알아보자.입력 N은 최대 26까지, 문자열의 길이는 최대 100,000..

문제 이해 단계 https://www.acmicpc.net/problem/3079 3079번: 입국심사 첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ M ≤ 1,000,000,000) 다음 N개 줄에는 각 심사대에서 심사를 하는데 걸리는 시간인 Tk가 주어진다. (1 ≤ Tk ≤ 109) www.acmicpc.net N개의 심사대와 M명이 주어진다. 각 심사대마다 심사하는데 소요되는 시간이 존재한다. M명은 한 줄로 서서 자기 차례를 기다리는데, 여러 개의 심사대 중 하나를 골라서 갈 수 있다. 이미 심사가 진행 중인 곳은 가지 못한다. 또한 몇 초를 기다렸다가 가는 것도 가능하다. 여러 가지 수를 조합해서 M명이 최대한 빨리 심사를 마치는 경우의 수를 조합할 때, 이때의 최소 ..