문제 이해 단계 https://www.acmicpc.net/problem/2473 2473번: 세 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 3 이상 5,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 www.acmicpc.net 정수로 되어있는 용액이 N개가 주어진다. 이 중에서 3개를 골라 3개의 합이 0에 가장 가까운 경우를 만들 때, 그때의 세 용액을 찾아서 오름차순으로 출력하는 것이 문제이다. 문제 접근 단계 문제는 상당히 간단한데, 일단 수의 범위랑 제한사항부터 살펴보자. 산성 용액과 알칼리 용액으로 구분해 놨지만, 사실상 용액의 범위는 -1,000,000,000 ~ 1,00..

문제 이해 단계 https://www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net N개의 건물이 있고, 각 건물마다 먼저 지어져야 하는 건설 순서가 K개 존재한다. 목표로 지어야 할 건물이 있을 때, 해당 건물을 짓는데 걸리는 최소 시간을 알아내는 문제 문제 접근 단계 일단 제한사항부터 살펴보자. 테스트 케이스 T의 개수는 명시되어있지 않다. 그리고 건물의 개수 N은 최대 1,000개 건설 순서 K의 개수와 최대 시간 소요시간은 100,000까지이다. 여기..

문제 이해 단계 https://www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net N x 3 짜리 맵이 존재한다. 각 칸에는 0 ~ 9 숫자가 적혀있다. 가장 윗 칸에서 한 칸씩 내려오는데, 내려올 수 있는 방향은 바로 아래 또는 대각 방향밖에 없다. 가장 위에서 아래로 이동할 때, 얻을 수 있는 최대 점수와 최수를 구하는 문제 문제 접근 단계 예제 입력을 통해 한번 유형을 찾아보려고 해 보자. 만약 내가 마지막 층(N)행의 2번째 칸인 9를 선택했다고 해보자. 이 입력에서 ..

문제 이해 단계 https://www.acmicpc.net/problem/11779 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net n개의 도시와 m개의 버스가 존재한다. 버스는 A도시에서 출발하여 B도시에 도착하는 정보로 주어진다. 그리고 각 버스마다 드는 비용이 존재한다. 또한 입력으로 출발지와 도착지가 주어질 때, 출발지에서 도착지까지 가는데 드는 최소 비용과 경로를 출력하는 것 문제 접근 단계 일단 문제 조건부터 살펴보자. 도시의 개수 n은 최대 1,000 간선의 개수(버..

문제 이해 단계 https://www.acmicpc.net/problem/2448 2448번: 별 찍기 - 11 첫째 줄에 N이 주어진다. N은 항상 3×2k 수이다. (3, 6, 12, 24, 48, ...) (0 ≤ k ≤ 10, k는 정수) www.acmicpc.net N = 24 일 때의 출력이다. 예제를 보고 규칙을 유추하고 별을 찍는 문제 입력 N은 무조건 3 * 2^k로 들어온다. 여기서 k의 범위는 0≤k≤10이다. 문제 접근 단계 별 찍기 시리즈 문제이다. 때문에 구현문제인 것 같은데, 어떤 식으로 구현해야 할까? k의 범위가 0부터 10까지니까 순서대로 해봤다. 이 이상은 그림이 너무 커질 것 같아서 k = 2 일 때까지만 그려보도록 하겠다. 이렇게 k가 1씩 커져갈 때의 규칙을 보면 ..

문제 이해 단계 https://www.acmicpc.net/problem/13172 13172번: Σ 모듈러가 11에서 1,000,000,007이 되어 답이 달라졌지만, 역시 3을 곱한 다음 1,000,000,007으로 나눈 나머지는 7이 된다. www.acmicpc.net 문제가 거의 비문학 지문이다. 여기서 문제 풀이에 필요한 정보만 뽑아보자. 1. 각 주사위에서 얻을 수 있는 기댓값은 a * b^(-1) modX를 계산해야 한다. 여기서 a는 모든 면에 적힌 숫자의 합이고, b는 주사위 면에 개수이다. 2. b^(-1)는 b의 모듈러 곱셈에 대한 역원인데, 구하는 방법은 b^(X-2) = b^(-1) modX이다. 3. 모든 주사위를 한 번씩 던졌을 때 나온 숫자들의 합의 기댓값을 얻기 위해서는 각..

문제 이해 단계 https://www.acmicpc.net/problem/12851 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net X좌표로만 이루어진 맵이 존재한다. 출발점 N과 도착점 K가 입력으로 들어온다. 출발점 N에서 할 수 있는 움직임은 총 3개이다. 1. X+1 2. X-1 3. X*2 3개의 움직임을 적절히 조합해서 도착점 K까지 갈 수 있는 가장 빠른 시간을 구하고, 가장 빠른 시간으로 갈 수 있는 경우의 수를 출력하는 문제 문제 접근 단계 숨바꼭질 시리즈 ..

문제 이해 단계 https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 바이토닉 수열이란 어떤 수를 A라고 했을 때, a d > e > f.. 이런 식으로 이루어져야 한다. 수열 A가 입력으로 들어올 때 그 수열의 부분이 바이토닉 수열이면서, 가장 긴 수열의 길이를 구하여 그 길이를 출력해라. 문제 접근 단계 가장 긴 ~~ 수열 시리즈 문제이다. 일단 제한사항부터 살펴보면, 수열의 길이는 최대 1000까지이다. 만약 시간복잡도가 O(n^2)까지 ..