문제 이해 단계 https://www.acmicpc.net/problem/16987 16987번: 계란으로 계란치기 원래 프로그래머의 기본 소양은 팔굽혀펴기를 단 한 개도 할 수 없는 것이라고 하지만 인범이는 3대 500을 넘기는 몇 안되는 프로그래머 중 한 명이다. 인범이는 BOJ에서 틀린 제출을 할 때마다 턱 www.acmicpc.net N개의 계란이 존재하고, 각 계란에는 (내구도, 무게) 정보가 쌍으로 주어진다.그리고 두 계란이 부딪힐 때 서로의 무게만큼 내구도가 깎여나간다. 내구도가 0 이하가 되면 계란이 깨지는 것으로 간주한다. 그리고 계란을 깨는 과정은 아래와 같이 한다. 1. 가장 왼쪽의 계란을 든다. 2. 손에 들고 있는 계란으로 깨지지 않은 다른 계란 중에서 하나를 친다. 단, 손에 든..

문제 이해 단계 https://www.acmicpc.net/problem/21939 21939번: 문제 추천 시스템 Version 1 tony9402는 최근 깃헙에 코딩테스트 대비 문제를 직접 뽑아서 "문제 번호, 난이도"로 정리해놨다. 깃헙을 이용하여 공부하시는 분들을 위해 새로운 기능을 추가해보려고 한다. 만들려고 하는 명령 www.acmicpc.net 문제가 N개 주어지는데, (문제의 번호, 난이도)의 쌍으로 이루어진다. 해당 조건일 때 recommend x로 나오는 출력을 그대로 구현해라는 문제 문제 접근 단계 문제 제한 사항부터 살펴보자. 문제의 개수 N은 최대 100,000개까지, 명령어 M의 개수는 10,000개이다. 최대 100,000개까지의 모든 탐색을 다한다고 해도 10^5 * 10^4..

문제 이해 단계 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/17073 17073번: 나무 위의 빗물 첫째 줄에 트리의 노드의 수 N과 1번 노드에 고인 물의 양을 의미하는 정수 W가 주어진다. (2 ≤ N ≤ 500,000, 1 ≤ W ≤ 109) 다음 N-1줄에 걸쳐, 트리에 존재하는 간선의 정보가 U V의 형태로 주어진다 www.acmicpc.net N개의 노드와 고인 물의 양 W가 주어진다. 루트 노드는 항상 1번으로 고정이다. 모든 노드는 루트 노드인 1번 노드의 자식 노드이다. 1번 노드로부터 물이 떨어지는데, 떨어지는 규칙은 다음과 같다. 1. 물을 가지고 있을 경우, 자식 노드가 있다면 자식 노드 중 하나를 골라 물을 1 준다. (자식 노드가 여러 개라면 동일한 확률로 하나를 ..

문제 이해 단계 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 자료형을 넘을 ..