문제 이해 단계 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)까지 ..
문제 이해 단계 https://www.acmicpc.net/problem/9935 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모 www.acmicpc.net 첫 번째 줄에 문장이 주어지고, 두 번째 줄에 폭발 문자열이라는 특정 키워드가 주어진다. 문장에서 폭발 키워드가 있으면 그 부분을 지운다. 그리고 문장을 이어 붙인다. 문장을 이어 붙였을 때, 또 키워드가 완성된다면 그 부분을 지운다. 이런 식으로 모든 폭발키워드를 지운 후, 남은 문장을 출력한다. 문제 접근 단계 제한사항부터 보자. 문장의 길이는 최대 1,000,0..
문제 이해 단계 https://www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 입력으로 정점의 개수 N과 간선의 개수 E가 주어진다. 여기서 간선은 양방향 그래프이다. 정점 1에서 정점 N까지 최단경로로 움직여야 하는데, 무조건 타깃으로 설정한 정점 A와 정점 B를 방문해야 한다. 여기서는 한번 이동했던 간선도 다시 이동하는 것을 허락한다. 이러한 조건일 때 두 정점을 반드시 거치면서 최단 경로로 이동할 때의 값을..
문제 이해 단계 https://www.acmicpc.net/problem/11444 11444번: 피보나치 수 6 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 피보나치 수열이 존재한다. n이 입력으로 들어올 때, n번째 수열의 값을 구하는 것이 문제. 문제 접근 단계 이 문제가 골드 2인 데는 제한사항 때문이다. 입력으로 들어올 수 있는 n이 10^18까지 가능하다. 엄청나게 크다. int 자료형으로는 절대 받을 수 없고 가장 큰 자료형인 long long int를 써야지만 받을 수 있다. 기존에 풀던 DP방식으로 문제를 풀면 시간 복잡도가 O(n)이 나온다. 이는 결국 1초가 넘어 시간초과가 나오기 때문에 다른 ..
문제 이해 단계 https://www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 입력으로 A, B, C가 들어온다. 자연수 A를 B번 곱하고, C로 나눈 나머지를 출력해라. 문제 접근 단계 상당히 간단한 문제로 보인다. 하지만 그렇지 않다. 여기에는 2가지의 문제점이 존재한다. 첫 번째는, 수의 범위이다. 제한사항을 보면 입력이 2,147,483,647까지다. 입력부터 20억이 넘어가기 때문에 20억^20억 long long int 자료형을 아득히 넘어간다. 그렇기 때문에 지수를 한 번에 곱해서 구해서는 안된다. 자료형을 넘..
문제 이해 단계 https://www.acmicpc.net/problem/2263 이진트리의 정점이 1~n까지의 번호가 중복 없이 매겨져 있다. 이진트리의 중위 순회와 후위 순회가 입력으로 주어질 때, 전위 순회를 출력하는 문제 문제 접근 단계 전위, 중위, 후위 순회의 개념과 특성을 미리 알고 있어야 한다. 전위 순회 : 루트 → 왼쪽 → 오른쪽 중위 순회 : 왼쪽 → 루트 → 오른쪽 후위 순회 : 왼쪽 → 오른쪽 → 루트 그림을 보면서 하는 것이 가장 빠르다. 중위 순회 : 7 3 8 1 9 4 10 0 11 5 2 6 후위 순회 : 7 8 3 9 10 4 1 11 5 6 2 0 이 된다. 우리는 이 2가지 정보를 가지고 전위 순회를 구해야 한다. 일단 후위 순회는 루트 노드가 마지막에 오기 때문에,..
문제 이해 단계 https://www.acmicpc.net/problem/22861 main 폴더 안에 있는 폴더의 총 개수 N과 파일의 총 개수 M이 주어진다. 그리고 폴더를 옮기는 횟수 K가 주어진다. 폴더를 옮긴다는 것은 폴더 A에 있던 하위 폴더와 파일들을 모두 폴더 B로 옮긴다는 것 그리고 마지막에 쿼리 Q가 주어지고, 그 쿼리에 맞는 파일의 종류가 몇 개인지, 그리고 파일의 수가 몇 개인지 출력하는 문제 사실문제가 상당히 길기 때문에, 링크를 타고 들어가서 문제를 읽고 오는 편이 낫다. 문제 접근 단계 입력으로 들어오는 것이 많다. 그렇기 때문에 더더욱 제한사항부터 살펴봐야 한다. 폴더(N)와 파일(M)의 개수는 최대 1,000개까지 가능하다. 파일을 옮기는 횟수(K)도 최대 1,000회까지 ..