CodeDrive

문제:

개똥벌레 한 마리가 장애물(석순과 종유석)로 가득찬 동굴에 들어갔다. 동굴의 길이는 N미터이고, 높이는 H미터이다. (N은 짝수) 첫 번째 장애물은 항상 석순이고, 그 다음에는 종유석과 석순이 번갈아가면서 등장한다.

아래 그림은 길이가 14미터이고 높이가 5미터인 동굴이다. (예제 그림)

이 개똥벌레는 장애물을 피하지 않는다. 자신이 지나갈 구간을 정한 다음 일직선으로 지나가면서 만나는 모든 장애물을 파괴한다.

위의 그림에서 4번째 구간으로 개똥벌레가 날아간다면 파괴해야하는 장애물의 수는 총 여덟개이다. (4번째 구간은 길이가 3인 석순과 길이가 4인 석순의 중간지점을 말한다)

하지만, 첫 번째 구간이나 다섯 번째 구간으로 날아간다면 개똥벌레는 장애물 일곱개만 파괴하면 된다.

동굴의 크기와 높이, 모든 장애물의 크기가 주어진다. 이때, 개똥벌레가 파괴해야하는 장애물의 최솟값과 그러한 구간이 총 몇 개 있는지 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 N과 H가 주어진다. N은 항상 짝수이다. (2 ≤ N ≤ 200,000, 2 ≤ H ≤ 500,000)

다음 N개 줄에는 장애물의 크기가 순서대로 주어진다. 장애물의 크기는 H보다 작은 양수이다.

출력:

첫째 줄에 개똥벌레가 파괴해야 하는 장애물의 최솟값과 그러한 구간의 수를 공백으로 구분하여 출력한다.

풀이방법:

이분 탐색을 사용하여, 빠르게 인덱스를 찾도록 한다. 석순과 종유석을 각자의 배열에 담고, 이들을 정렬한다. 그리고 H를 늘려가며, 부셔야 하는 갯수를 찾는데, 개똥벌레는 정수의 높이로 날라가는 것이 아닌 0.5 지점을 날기 때문에 이를 고려하여 인덱스를 찾아야 한다. 종유석과 석순 개별적으로 부셔야 하는 갯수를 찾은 뒤 이들의 합이 가장 작을 때를 찾도록 한다.

 만약 최솟값이 여러번 나오는 경우에는 이를 누적해서 더해주고, 만약 새로운 최솟값이 나오면 누적 합을 초기화시켜준다.

문제링크:

https://www.acmicpc.net/problem/3020

문제:

당신은 상범 빌딩에 갇히고 말았다. 여기서 탈출하는 가장 빠른 길은 무엇일까? 상범 빌딩은 각 변의 길이가 1인 정육면체(단위 정육면체)로 이루어져있다. 각 정육면체는 금으로 이루어져 있어 지나갈 수 없거나, 비어있어서 지나갈 수 있게 되어있다. 당신은 각 칸에서 인접한 6개의 칸(동,서,남,북,상,하)으로 1분의 시간을 들여 이동할 수 있다. 즉, 대각선으로 이동하는 것은 불가능하다. 그리고 상범 빌딩의 바깥면도 모두 금으로 막혀있어 출구를 통해서만 탈출할 수 있다.

당신은 상범 빌딩을 탈출할 수 있을까? 만약 그렇다면 얼마나 걸릴까?

입력:

입력은 여러 개의 테스트 케이스로 이루어지며, 각 테스트 케이스는 세 개의 정수 L, R, C로 시작한다. L(1 ≤ L ≤ 30)은 상범 빌딩의 층 수이다. R(1 ≤ R ≤ 30)과 C(1 ≤ C ≤ 30)는 상범 빌딩의 한 층의 행과 열의 개수를 나타낸다.

그 다음 각 줄이 C개의 문자로 이루어진 R개의 행이 L번 주어진다. 각 문자는 상범 빌딩의 한 칸을 나타낸다. 금으로 막혀있어 지나갈 수 없는 칸은 '#'으로 표현되고, 비어있는 칸은 '.'으로 표현된다. 당신의 시작 지점은 'S'로 표현되고, 탈출할 수 있는 출구는 'E'로 표현된다. 각 층 사이에는 빈 줄이 있으며, 입력의 끝은 L, R, C가 모두 0으로 표현된다. 시작 지점과 출구는 항상 하나만 있다.

출력:

각 빌딩에 대해 한 줄씩 답을 출력한다. 만약 당신이 탈출할 수 있다면 다음과 같이 출력한다.

Escaped in x minute(s).

여기서 x는 상범 빌딩을 탈출하는 데에 필요한 최단 시간이다.

만일 탈출이 불가능하다면, 다음과 같이 출력한다.

Trapped!

풀이방법:

 상하좌우로만 움직이는 일반 그래프 문제와 다르게 위, 아래의 개념이 추가된 문제다. 따라서 기존 2중 배열로 구성되던 visited 배열을 3중 배열로 바꿔서 풀도록 한다.

 첫 시작점을 찾은 뒤에 BFS를 통해 움직일 수 없을 때까지 계속 움직이고, 만약 목적지에 도달하면 그 때의 시간을 반환하고, 그렇지 못하면 0을 반환하게 한다.

문제링크:

https://www.acmicpc.net/problem/6593

문제:

수빈이는 A와 B로만 이루어진 영어 단어가 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다.

이런 사실에 놀란 수빈이는 간단한 게임을 만들기로 했다. 두 문자열 S와 T가 주어졌을 때, S를 T로 바꾸는 게임이다. 문자열을 바꿀 때는 다음과 같은 두 가지 연산만 가능하다.

• 문자열의 뒤에 A를 추가한다.
• 문자열을 뒤집고 뒤에 B를 추가한다.

주어진 조건을 이용해서 S를 T로 만들 수 있는지 없는지 알아내는 프로그램을 작성하시오. 

입력:

첫째 줄에 S가 둘째 줄에 T가 주어진다. (1 ≤ S의 길이 ≤ 999, 2 ≤ T의 길이 ≤ 1000, S의 길이 < T의 길이)

출력:

S를 T로 바꿀 수 있으면 1을 없으면 0을 출력한다.

풀이방법:

 S를 T로 바꾸는 방법에 대해 찾는 것이 아니라 T에서 S로 그리디하게 되돌아가는 방법으로 만들 수 있는지 없는지 확인한다.

 두 가지 연산은 맨 뒤에 A가 추가되거나 B가 추가된다. 따라서 매번 T의 맨 끝에 따라 연산을 수행하도록 한다. 맨 마지막이 A라면 A만 떼어내고, B라면 B를 떼어내고 뒤집어서 새로 T를 만들어내도록 한다.

 T와 S의 길이가 같아졌을 때, S와 T가 같다면 1을 같지않다면 0을 출력한다.

문제링크:

https://www.acmicpc.net/problem/12904

문제:

1부터 N까지의 수를 임의로 배열한 순열은 총 N! = N×(N-1)×…×2×1 가지가 있다.

임의의 순열은 정렬을 할 수 있다. 예를 들어  N=3인 경우 {1, 2, 3}, {1, 3, 2}, {2, 1, 3}, {2, 3, 1}, {3, 1, 2}, {3, 2, 1}의 순서로 생각할 수 있다. 첫 번째 수가 작은 것이 순서상에서 앞서며, 첫 번째 수가 같으면 두 번째 수가 작은 것이, 두 번째 수도 같으면 세 번째 수가 작은 것이….

N이 주어지면, 아래의 두 소문제 중에 하나를 풀어야 한다. k가 주어지면 k번째 순열을 구하고, 임의의 순열이 주어지면 이 순열이 몇 번째 순열인지를 출력하는 프로그램을 작성하시오.

입력:

첫째 줄에 N(1≤N≤20)이 주어진다. 둘째 줄의 첫 번째 수는 소문제 번호이다. 1인 경우 k(1≤k≤N!)를 입력받고, 2인 경우 임의의 순열을 나타내는 N개의 수를 입력받는다. N개의 수에는 1부터 N까지의 정수가 한 번씩만 나타난다.

출력:

k번째 수열을 나타내는 N개의 수를 출력하거나, 몇 번째 수열인지를 출력하면 된다.

풀이방법:

 한 문제에 K번째 수열을 구하는 문제와 주어진 수열이 몇 번째인지 구하는 문제가 합쳐져 있다. 두 소문제는 주어진 수 중 맨 앞의 숫자로 구별되며, 이를 command(c)로 구분해 각 소문제를 풀도록 한다.

 첫 번째 소문제는 K번째 수열을 구하는 문제다. 앞의 자릿수부터 계산하며, 주어진 수 K로부터 만들 수 있는 경우의 수를 빼주며 한자리씩 정해나간다. 즉, 예제의 경우 3번째 수열을 구하는 문제에서 맨 앞자리를 a인 경우의 수는 3!개이다. 따라서 3번째 수열은 0~3!번째 수열에 속할 것이므로, 맨 앞자리는 1인 것을 알 수 있다. 이러한 방법을 계속하여 k번째 수열을 찾는다.

 두 번째 소문제는 첫 번째 소문제의 역으로 구할 수 있다. 팩토리얼을 사용해 k번째 수열을 구했던 것의 역으로 팩토리얼을 더하면서 k를 찾도록 한다.

문제링크:

https://www.acmicpc.net/problem/1722

문제:

무한 수열 A는 다음과 같다.

• A0 = 1
• Ai = A⌊i/P⌋ + A⌊i/Q⌋ (i ≥ 1)

N, P와 Q가 주어질 때, AN을 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 3개의 정수 N, P, Q가 주어진다.

출력:

첫째 줄에 AN을 출력한다.

풀이방법:

 문제에서 명확하게 점화식이 주어졌기 때문에 다이나믹 프로그래밍을 사용하도록 한다. 하지만 주어진 조건의 N, P, Q이 매우 크기 때문에 list를 사용해서 구현을 한다면 메모리가 터지는 문제점이 있다. 따라서 최대한 쓰지 않는(비어있는) 값들을 줄이기 위해서 dict 자료형에다가 값들을 mapping 하도록 한다. 빠른 구현을 위해서 defaultdict을 사용해 초기화하는 과정을 간단하게 구현할 수 있도록 했다.

문제링크:

https://www.acmicpc.net/problem/1351

문제:

세계적인 도둑 상덕이는 보석점을 털기로 결심했다.

상덕이가 털 보석점에는 보석이 총 N개 있다. 각 보석은 무게 Mi와 가격 Vi를 가지고 있다. 상덕이는 가방을 K개 가지고 있고, 각 가방에 담을 수 있는 최대 무게는 Ci이다. 가방에는 최대 한 개의 보석만 넣을 수 있다.

상덕이가 훔칠 수 있는 보석의 최대 가격을 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000)

다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000)

다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci ≤ 100,000,000)

모든 숫자는 양의 정수이다.

출력:

첫째 줄에 상덕이가 훔칠 수 있는 보석 가격의 합의 최댓값을 출력한다.

풀이방법:

 우선순위 큐(heapq)를 사용해서 가방에 최대한 비싼 보석을 그리디하게 넣는다 생각하면 된다. 따라서 보석의 정보들을 무게가 가벼운 순으로 heapq를 통해서 정렬하고, 가방도 오름차순으로 정렬을 한다.

 정렬을 마친 뒤에 가벼운 가방으로부터 시작하여 해당 가방에 넣을 수 있는 보석들을 최대힙으로 다시 구현을 한 뒤에 그 최대힙에서 가장 큰 값을 뽑아 answer에 더해준다. 이와 같은 과정들을 모든 가방에 대해 수행을 하며, 최대힙과 최소힙은 계속해서 누적해서 사용하도록 한다.

문제링크:

https://www.acmicpc.net/problem/1202

문제:

김지민은 N명이 참가하는 스타 토너먼트에 진출했다. 토너먼트는 다음과 같이 진행된다. 일단 N명의 참가자는 번호가 1번부터 N번까지 배정받는다. 그러고 난 후에 서로 인접한 번호끼리 스타를 한다. 이긴 사람은 다음 라운드에 진출하고, 진 사람은 그 라운드에서 떨어진다. 만약 그 라운드의 참가자가 홀수명이라면, 마지막 번호를 가진 참가자는 다음 라운드로 자동 진출한다. 다음 라운드에선 다시 참가자의 번호를 1번부터 매긴다. 이때, 번호를 매기는 순서는 처음 번호의 순서를 유지하면서 1번부터 매긴다. 이 말은 1번과 2번이 스타를 해서 1번이 진출하고, 3번과 4번이 스타를 해서 4번이 진출했다면, 4번은 다음 라운드에서 번호 2번을 배정받는다. 번호를 다시 배정받은 후에 한 명만 남을 때까지 라운드를 계속 한다.

마침 이 스타 대회에 임한수도 참가했다. 김지민은 갑자기 스타 대회에서 우승하는 욕심은 없어지고, 몇 라운드에서 임한수와 대결하는지 궁금해졌다. 일단 김지민과 임한수는 서로 대결하기 전까지 항상 이긴다고 가정한다. 1 라운드에서 김지민의 번호와 임한수의 번호가 주어질 때, 과연 김지민과 임한수가 몇 라운드에서 대결하는지 출력하는 프로그램을 작성하시오.

입력:

첫째 줄에 참가자의 수 N과 1 라운드에서 김지민의 번호와 임한수의 번호가 순서대로 주어진다. N은 100,000보다 작거나 같은 자연수이고, 김지민의 번호와 임한수의 번호는 N보다 작거나 같은 자연수이고, 서로 다르다.

출력:

첫째 줄에 김지민과 임한수가 대결하는 라운드 번호를 출력한다. 만약 서로 대결하지 않을 때는 -1을 출력한다.

풀이방법:

 주어진 조건에 따라 수행하게 하는 구현문제다. 앞에서부터 순차적으로 두 사람을 뽑은 뒤에 각 사람이 k와 l인지 확인하고, 둘 중 하나에 해당하면 그 사람이 무조건 이기게 한다. 만약 각각 k와 l에 해당하면 반복문을 중단시킨다.(만약 둘다 아니라면 먼저 들어온 사람을 이기게 한다.) 

문제링크:

https://www.acmicpc.net/problem/1057

문제:

크기가 N×N인 지도가 있다. 지도의 각 칸에는 그 곳의 높이가 적혀져 있다.

오늘은 이 지도에서 지나갈 수 있는 길이 몇 개 있는지 알아보려고 한다. 길이란 한 행 또는 한 열 전부를 나타내며, 한쪽 끝에서 다른쪽 끝까지 지나가는 것이다. 

다음과 같은 N=6인 경우 지도를 살펴보자.

이때, 길은 총 2N개가 있으며, 아래와 같다.

길을 지나갈 수 있으려면 길에 속한 모든 칸의 높이가 모두 같아야 한다. 또는, 경사로를 놓아서 지나갈 수 있는 길을 만들 수 있다. 경사로는 높이가 항상 1이며, 길이는 L이다. 또, 개수는 매우 많아 부족할 일이 없다. 경사로는 낮은 칸과 높은 칸을 연결하며, 아래와 같은 조건을 만족해야한다.

• 경사로는 낮은 칸에 놓으며, L개의 연속된 칸에 경사로의 바닥이 모두 접해야 한다.
• 낮은 칸과 높은 칸의 높이 차이는 1이어야 한다.
• 경사로를 놓을 낮은 칸의 높이는 모두 같아야 하고, L개의 칸이 연속되어 있어야 한다.

아래와 같은 경우에는 경사로를 놓을 수 없다.

• 경사로를 놓은 곳에 또 경사로를 놓는 경우
• 낮은 칸과 높은 칸의 높이 차이가 1이 아닌 경우
• 낮은 지점의 칸의 높이가 모두 같지 않거나, L개가 연속되지 않은 경우
• 경사로를 놓다가 범위를 벗어나는 경우

L = 2인 경우에 경사로를 놓을 수 있는 경우를 그림으로 나타내면 아래와 같다.

경사로를 놓을 수 없는 경우는 아래와 같다.

위의 그림의 가장 왼쪽부터 1번, 2번, 3번, 4번 예제라고 했을 때, 1번은 높이 차이가 1이 아니라서, 2번은 경사로를 바닥과 접하게 놓지 않아서, 3번은 겹쳐서 놓아서, 4번은 기울이게 놓아서 불가능한 경우이다.

가장 위에 주어진 그림 예의 경우에 지나갈 수 있는 길은 파란색으로, 지나갈 수 없는 길은 빨간색으로 표시되어 있으며, 아래와 같다. 경사로의 길이 L = 2이다.

지도가 주어졌을 때, 지나갈 수 있는 길의 개수를 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다.

출력:

첫째 줄에 지나갈 수 있는 길의 개수를 출력한다.

풀이방법:

check 함수를 사용해서 가로에 대해서 먼저 체크하고, 행과 열을 바꿔 세로에 대해서 체크하도록 한다.

check 함수 내에서는 현재값과 다음값의 높이 차이에 대해서 확인하고, 같다면 그대로 넘어간다. 만약 차이가 1보다 크다면 경사로를 놓을 수 없는 경우이기 때문에 0을 반환한다.

 만약 1 혹은 -1만큼의 차이가 나면 그 위치로부터 L의 경사로를 놓을 수 있는지 확인한다. 이 때 확인해야 하는 것은 낮은 지점의 높이가 L개 만큼 연속되는지, 이미 경사로가 놓아져 있는지 확인해야 한다. 이 과정이 모두 확인되면 visited배열에 경사로를 놓으며 넘어가고 그렇지 않다면 0을 반환하도록 한다. 이렇게 끝까지 탐색했는데 문제가 없는 경우라면 answer에 1을 더하도록 한다.

 모든 탐색을 마친 뒤에 answer 값을 출력하도록 한다.

문제링크:

https://www.acmicpc.net/problem/14890

문제:

2차원 세계에 블록이 쌓여있다. 비가 오면 블록 사이에 빗물이 고인다.

비는 충분히 많이 온다. 고이는 빗물의 총량은 얼마일까?

입력:

첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500)

두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치부터 차례대로 W개 주어진다.

따라서 블록 내부의 빈 공간이 생길 수 없다. 또 2차원 세계의 바닥은 항상 막혀있다고 가정하여도 좋다.

출력:

2차원 세계에서는 한 칸의 용량은 1이다. 고이는 빗물의 총량을 출력하여라.

빗물이 전혀 고이지 않을 경우 0을 출력하여라.

풀이방법:

 양 끝점을 제외한 칸에서부터 왼쪽과 오른쪽을 각각 탐색해서 가장 낮은 위치를 찾아내고, 왼쪽의 가장 낮은 위치와 오른쪽의 가장 낮은 위치 더 낮은 값이 해당 칸에 빗물이 고인 수치다. 이 과정을 모든 칸에 진행하면서 값을 누적시키면 최종 답을 구할 수 있다.

문제링크:

https://www.acmicpc.net/problem/14719

문제:

KOI 부설 과학연구소에서는 많은 종류의 산성 용액과 알칼리성 용액을 보유하고 있다. 각 용액에는 그 용액의 특성을 나타내는 하나의 정수가 주어져있다.  산성 용액의 특성값은 1부터 1,000,000,000까지의 양의 정수로 나타내고, 알칼리성 용액의 특성값은 -1부터 -1,000,000,000까지의 음의 정수로 나타낸다.

같은 양의 두 용액을 혼합한 용액의 특성값은 혼합에 사용된 각 용액의 특성값의 합으로 정의한다. 이 연구소에서는 같은 양의 두 용액을 혼합하여 특성값이 0에 가장 가까운 용액을 만들려고 한다. 

예를 들어, 주어진 용액들의 특성값이 [-2, 4, -99, -1, 98]인 경우에는 특성값이 -99인 용액과 특성값이 98인 용액을 혼합하면 특성값이 -1인 용액을 만들 수 있고, 이 용액이 특성값이 0에 가장 가까운 용액이다. 참고로, 두 종류의 알칼리성 용액만으로나 혹은 두 종류의 산성 용액만으로 특성값이 0에 가장 가까운 혼합 용액을 만드는 경우도 존재할 수 있다.

산성 용액과 알칼리성 용액의 특성값이 주어졌을 때, 이 중 두 개의 서로 다른 용액을 혼합하여 특성값이 0에 가장 가까운 용액을 만들어내는 두 용액을 찾는 프로그램을 작성하시오.

입력:

첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,000,000 이하이다. N개의 용액들의 특성값은 모두 다르고, 산성 용액만으로나 알칼리성 용액만으로 입력이 주어지는 경우도 있을 수 있다.

출력:

첫째 줄에 특성값이 0에 가장 가까운 용액을 만들어내는 두 용액의 특성값을 출력한다. 출력해야 하는 두 용액은 특성값의 오름차순으로 출력한다. 특성값이 0에 가장 가까운 용액을 만들어내는 경우가 두 개 이상일 경우에는 그 중 아무것이나 하나를 출력한다.

풀이방법:

 투 포인터를 양쪽 끝값에 두고, 하나씩 이동시키면서 0에 가장 가까운 용액을 만들어 나가도록 한다. 포인터에 있는 값을 비교하고, start 값이 크다면 start를 이동하고, end가 크다면 end를 이동시키도록 한다. 이렇게 생성되는 용액의 특성값과 포인터 값들을 min_heap 정렬해두고, 모든 탐색을 마친 뒤에 min heap의 첫 값을 가져와서 출력하도록 한다.

문제링크:

https://www.acmicpc.net/problem/2470