문제 이해 단계 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명이 최대한 빨리 심사를 마치는 경우의 수를 조합할 때, 이때의 최소 ..

문제 이해 단계 https://www.acmicpc.net/problem/16928 16928번: 뱀과 사다리 게임 첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으 www.acmicpc.net 10x10 짜리 맵에 사다리와 뱀과 맵이 있다. 그리고 플레이어는 1~6까지 적혀있는 주사위로 움직인다. 목표는 1에서 100까지 움직이는 것이다. 주사위 결과가 100칸을 넘어서 움직이는 것이라면 이동할 수 없다. 사다리와 뱀은 둘 다 점프 개념으로 사다리는 뒤에서 앞으로, 뱀은 앞에서 뒤로 이동하는 개념이다. N개의 사다리와 M개의..

문제 이해 단계 https://www.acmicpc.net/problem/20955 20955번: 민서의 응급 수술 민서는 강원대학교 컴퓨터공학과의 신임 교수이다. 그녀가 저술한 효율적인 택배 배달을 위한 최적 경로 설계에 관한 연구 논문은 아직도 널리 인용되고 있다. 오늘도 열심히 강의를 하던 민서 www.acmicpc.net 뉴런(노드) N개와 시냅스(간선) M개가 들어온다. 이후 M 줄에 걸쳐 연결된 두 뉴런의 정보가 들어온다. 만들어야 하는 것은 하나로 연결된 트리, 즉 사이클이 존재하지 않아야 한다. 만약 사이클이 존재한다면 그 사이클을 끊어야 한다. 이러한 조건일 때 모든 뉴런을 하나의 연결된 트리로 만들 때 필요한 최소 연산 횟수를 구하는 문제 문제 접근 단계 문제에서 대놓고 뉴런과 시냅스,..

문제 이해 단계 https://www.acmicpc.net/problem/18866 18866번: 젊은 날의 생이여 욱제의 젊은 날이 될 수 있는 최대 기간, 즉 문제의 조건을 만족할 수 있는 최대의 1 ≤ K > N; for(int i = 0; i > v1 >> v2; v[i][0]= v1; v[i][1]= v2; } int young[N][2], old[N][2]; // 젊은날, 늙은날 최대 최소 정보 int max_happy = 0; int min_happy = INT32_MAX; int max_tired = 0; int min_tired = INT32_MAX; // 젊은 날은 1부터 ~ K까지 for(int i = 0; i < N; i++){ // ..

문제 이해 단계 https://www.acmicpc.net/problem/16398 16398번: 행성 연결 홍익 제국의 중심은 행성 T이다. 제국의 황제 윤석이는 행성 T에서 제국을 효과적으로 통치하기 위해서, N개의 행성 간에 플로우를 설치하려고 한다. 두 행성 간에 플로우를 설치하면 제국의 함 www.acmicpc.net 행성의 수 N개가 입력으로 들어온다. 이후 행성 간 관리 비용이 NxN 행렬로 들어오는데, 각각 C_ij로 i와 j 사이의 비용을 뜻한다. (i = j인 경우 0) 행성 N개를 모두 연결하는데 드는 비용을 최소화할 때, 최소화한 비용을 구하는 문제 문제 접근 단계 조건부터 보자면 행성의 수 N은 최대 1000개까지이다. 즉 NxN 행렬은 1,000,000개까지 생성될 수 있다. 그..