CodeDrive

문제:

N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다.

아기 상어와 물고기는 모두 크기를 가지고 있고, 이 크기는 자연수이다. 가장 처음에 아기 상어의 크기는 2이고, 아기 상어는 1초에 상하좌우로 인접한 한 칸씩 이동한다.

아기 상어는 자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없고, 나머지 칸은 모두 지나갈 수 있다. 아기 상어는 자신의 크기보다 작은 물고기만 먹을 수 있다. 따라서, 크기가 같은 물고기는 먹을 수 없지만, 그 물고기가 있는 칸은 지나갈 수 있다.

아기 상어가 어디로 이동할지 결정하는 방법은 아래와 같다.

• 더 이상 먹을 수 있는 물고기가 공간에 없다면 아기 상어는 엄마 상어에게 도움을 요청한다.
• 먹을 수 있는 물고기가 1마리라면, 그 물고기를 먹으러 간다.
• 먹을 수 있는 물고기가 1마리보다 많다면, 거리가 가장 가까운 물고기를 먹으러 간다.
  • 거리는 아기 상어가 있는 칸에서 물고기가 있는 칸으로 이동할 때, 지나야하는 칸의 개수의 최솟값이다.
  • 거리가 가까운 물고기가 많다면, 가장 위에 있는 물고기, 그러한 물고기가 여러마리라면, 가장 왼쪽에 있는 물고기를 먹는다.

아기 상어의 이동은 1초 걸리고, 물고기를 먹는데 걸리는 시간은 없다고 가정한다. 즉, 아기 상어가 먹을 수 있는 물고기가 있는 칸으로 이동했다면, 이동과 동시에 물고기를 먹는다. 물고기를 먹으면, 그 칸은 빈 칸이 된다.

아기 상어는 자신의 크기와 같은 수의 물고기를 먹을 때 마다 크기가 1 증가한다. 예를 들어, 크기가 2인 아기 상어는 물고기를 2마리 먹으면 크기가 3이 된다.

공간의 상태가 주어졌을 때, 아기 상어가 몇 초 동안 엄마 상어에게 도움을 요청하지 않고 물고기를 잡아먹을 수 있는지 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 공간의 크기 N(2 ≤ N ≤ 20)이 주어진다.

둘째 줄부터 N개의 줄에 공간의 상태가 주어진다. 공간의 상태는 0, 1, 2, 3, 4, 5, 6, 9로 이루어져 있고, 아래와 같은 의미를 가진다.

• 0: 빈 칸
• 1, 2, 3, 4, 5, 6: 칸에 있는 물고기의 크기
• 9: 아기 상어의 위치

아기 상어는 공간에 한 마리 있다.

출력:

첫째 줄에 아기 상어가 엄마 상어에게 도움을 요청하지 않고 물고기를 잡아먹을 수 있는 시간을 출력한다.

풀이방법:

 BFS를 통해 아기 상어가 먹을 수 있는 물고기를 찾은 후에 문제 조건에 맞게 정렬하여 하나씩 먹으면 된다.

무한 while을 사용하며 엄마 상어를 호출할 경우(탐색했지만 먹을 수 있는 물고기가 없는 경우)에만 빠져나올 수 있도록 한다. eat_fish함수를 통해 탐색하며 일반적인 bfs 알고리즘을 사용한다. 이 때, 빠른 탐색을 위해 좌표만을 저장하는 것이 아닌 distance도 구해서 먹을 수 있는 물고기를 찾는 조건을 한번의 sort로 찾을 수 있도록 한다.

 먹을 수 있는 물고기를 찾은 경우에는 maps를 최신화하고, 아기 상어의 size를 늘린다. 이 때, 아기 상어의 size가 커진 경우에는 count를 초기화 시키도록 한다. (2개 먹음 -> 성장 -> 다시 3개 먹음 -> 성장 -> ...)

 BFS 과정에서 찾은 distance를 시간에 더하도록 하며, 못 찾을 때 while을 나와 time을 출력한다.

문제링크:

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

문제:

스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감시할 수 있는 방법은 다음과 같다.

1번 CCTV는 한 쪽 방향만 감시할 수 있다. 2번과 3번은 두 방향을 감시할 수 있는데, 2번은 감시하는 방향이 서로 반대방향이어야 하고, 3번은 직각 방향이어야 한다. 4번은 세 방향, 5번은 네 방향을 감시할 수 있다.

CCTV는 감시할 수 있는 방향에 있는 칸 전체를 감시할 수 있다. 사무실에는 벽이 있는데, CCTV는 벽을 통과할 수 없다. CCTV가 감시할 수 없는 영역은 사각지대라고 한다.

CCTV는 회전시킬 수 있는데, 회전은 항상 90도 방향으로 해야 하며, 감시하려고 하는 방향이 가로 또는 세로 방향이어야 한다.

지도에서 0은 빈 칸, 6은 벽, 1~5는 CCTV의 번호이다. 위의 예시에서 1번의 방향에 따라 감시할 수 있는 영역을 '#'로 나타내면 아래와 같다.

CCTV는 벽을 통과할 수 없기 때문에, 1번이 → 방향을 감시하고 있을 때는 6의 오른쪽에 있는 칸을 감시할 수 없다.

위의 예시에서 감시할 수 있는 방향을 알아보면 아래와 같다.

CCTV는 CCTV를 통과할 수 있다. 아래 예시를 보자.

위와 같은 경우에 2의 방향이 ↕ 3의 방향이 ←와 ↓인 경우 감시받는 영역은 다음과 같다.

사무실의 크기와 상태, 그리고 CCTV의 정보가 주어졌을 때, CCTV의 방향을 적절히 정해서, 사각 지대의 최소 크기를 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 사무실의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 8)

둘째 줄부터 N개의 줄에는 사무실 각 칸의 정보가 주어진다. 0은 빈 칸, 6은 벽, 1~5는 CCTV를 나타내고, 문제에서 설명한 CCTV의 종류이다. 

CCTV의 최대 개수는 8개를 넘지 않는다.

출력:

첫째 줄에 사각 지대의 최소 크기를 출력한다.

풀이방법:

 CCTV 번호에 따라 감시할 수 있는 방향이 다르고, 같은 번호라도 회전이 가능하기 때문에 같은 번호도 서로 다른 방향을 가리킬 수 있다. 각 번호에 따라 나올 수 있는 경우의 수는 동,서,남,북 4가지 경우밖에 없다. 따라서 CCTV 번호에 따라 기준이 되는 축을 기준으로 동,서,남,북으로 각각 배정을 해보며 사각지대가 최소가 되는 경우를 찾도록 한다. 즉, 백트래킹을 사용해 모든 경우에 대해 계산한다고 생각하면 된다.

 cctv를 설정하기에 앞서서 지도 상의 cctv의 개수와 좌표를 먼저 배열에 담아둔다. 이 배열을 기준으로 모든 cctv가 배치되었는지 확인하기 때문이다. 이 작업을 모두 마친 뒤 cctv를 하나씩 배치하도록 한다. 방향에 따라, 번호에 따라 cctv를 설정하며, 매 cctv 설정마다 visited를 최신화하여 사각지대를 계산할 수 있도록 한다. 또한 같은 번호의 cctv를 추후 회전하는 것을 고려하기 위해 rollback이라는 배열에 cctv가 탐색할 수 있는 좌표들을 담아 다시 되돌릴 수 있도록 한다.

 cctv를 모두 설정할 때마다 사각지대의 수를 구하며, 그 중 가장 최소인 값을 출력하도록 한다.

문제링크:

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

문제:

폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다.

• 정사각형은 서로 겹치면 안 된다.
• 도형은 모두 연결되어 있어야 한다.
• 정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다.

정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 다음과 같은 5가지가 있다.

아름이는 크기가 N×M인 종이 위에 테트로미노 하나를 놓으려고 한다. 종이는 1×1 크기의 칸으로 나누어져 있으며, 각각의 칸에는 정수가 하나 쓰여 있다.

테트로미노 하나를 적절히 놓아서 테트로미노가 놓인 칸에 쓰여 있는 수들의 합을 최대로 하는 프로그램을 작성하시오.

테트로미노는 반드시 한 정사각형이 정확히 하나의 칸을 포함하도록 놓아야 하며, 회전이나 대칭을 시켜도 된다.

입력:

첫째 줄에 종이의 세로 크기 N과 가로 크기 M이 주어진다. (4 ≤ N, M ≤ 500)

둘째 줄부터 N개의 줄에 종이에 쓰여 있는 수가 주어진다. i번째 줄의 j번째 수는 위에서부터 i번째 칸, 왼쪽에서부터 j번째 칸에 쓰여 있는 수이다. 입력으로 주어지는 수는 1,000을 넘지 않는 자연수이다.

출력:

첫째 줄에 테트로미노가 놓인 칸에 쓰인 수들의 합의 최댓값을 출력한다.

풀이방법:

 정사각형 4개를 이어 붙인 폴리오미노인 테트로미노는 회전과 대칭을 포함해도 경우의 수가 많지 않다. 따라서 모든 경우의 수를 포함하고 있는 shape_list를 만든 후에 모든 점마다 테트로미노를 하나씩 넣어보며 가장 최대가 되는 경우를 찾는다.

문제링크:

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

문제:

1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여 6번만 키를 비교하였고, 그 결과가 다음과 같다고 하자.

• 1번 학생의 키 < 5번 학생의 키
• 3번 학생의 키 < 4번 학생의 키
• 5번 학생의 키 < 4번 학생의 키
• 4번 학생의 키 < 2번 학생의 키
• 4번 학생의 키 < 6번 학생의 키
• 5번 학생의 키 < 2번 학생의 키

이 비교 결과로부터 모든 학생 중에서 키가 가장 작은 학생부터 자신이 몇 번째인지 알 수 있는 학생들도 있고 그렇지 못한 학생들도 있다는 사실을 아래처럼 그림을 그려 쉽게 확인할 수 있다. a번 학생의 키가 b번 학생의 키보다 작다면, a에서 b로 화살표를 그려서 표현하였다. 

1번은 5번보다 키가 작고, 5번은 4번보다 작기 때문에, 1번은 4번보다 작게 된다. 그러면 1번, 3번, 5번은 모두 4번보다 작게 된다. 또한 4번은 2번과 6번보다 작기 때문에, 4번 학생은 자기보다 작은 학생이 3명이 있고, 자기보다 큰 학생이 2명이 있게 되어 자신의 키가 몇 번째인지 정확히 알 수 있다. 그러나 4번을 제외한 학생들은 자신의 키가 몇 번째인지 알 수 없다.

학생들의 키를 비교한 결과가 주어질 때, 자신의 키가 몇 번째인지 알 수 있는 학생들이 모두 몇 명인지 계산하여 출력하는 프로그램을 작성하시오.

입력:

첫째 줄에 학생들의 수 N (2 ≤ N ≤ 500)과 두 학생 키를 비교한 횟수 M (0 ≤ M ≤ N(N-1)/2)이 주어진다. 다음 M개의 각 줄에는 두 학생의 키를 비교한 결과를 나타내는 두 양의 정수 a와 b가 주어진다. 이는 번호가 a인 학생이 번호가 b인 학생보다 키가 작은 것을 의미한다. 

출력:

자신이 키가 몇 번째인지 알 수 있는 학생이 모두 몇 명인지를 출력한다. 

풀이방법:

 자신을 기준으로 다른 사람에게 도달할 수 있다. 즉, 비교를 할 수 있는 사람이 몇명인지 확인하도록 한다. 자신보다 큰 사람과 자신보다 작은 사람이 N-1명이면 자신의 키가 몇 번째인지 알 수 있다.

 따라서 플로이드 와샬을 사용해서 이 문제를 풀도록 한다. 플로이드 와샬은 모든 꼭짓점 쌍 간의 최단 경로의 길이를 알 수 있는 알고리즘인데, 이 문제에 알맞게 몇명과 비교를 할 수 있는지 여부로 수정하여 문제를 해결하도록 한다.

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

문제:

상어 초등학교에는 교실이 하나 있고, 교실은 N×N 크기의 격자로 나타낼 수 있다. 학교에 다니는 학생의 수는 N2명이다. 오늘은 모든 학생의 자리를 정하는 날이다. 학생은 1번부터 N2번까지 번호가 매겨져 있고, (r, c)는 r행 c열을 의미한다. 교실의 가장 왼쪽 윗 칸은 (1, 1)이고, 가장 오른쪽 아랫 칸은 (N, N)이다.

선생님은 학생의 순서를 정했고, 각 학생이 좋아하는 학생 4명도 모두 조사했다. 이제 다음과 같은 규칙을 이용해 정해진 순서대로 학생의 자리를 정하려고 한다. 한 칸에는 학생 한 명의 자리만 있을 수 있고, |r1 - r2| + |c1 - c2| = 1을 만족하는 두 칸이 (r1, c1)과 (r2, c2)를 인접하다고 한다.

1. 비어있는 칸 중에서 좋아하는 학생이 인접한 칸에 가장 많은 칸으로 자리를 정한다.
2. 1을 만족하는 칸이 여러 개이면, 인접한 칸 중에서 비어있는 칸이 가장 많은 칸으로 자리를 정한다.
3. 2를 만족하는 칸도 여러 개인 경우에는 행의 번호가 가장 작은 칸으로, 그러한 칸도 여러 개이면 열의 번호가 가장 작은 칸으로 자리를 정한다.

예를 들어, N = 3이고, 학생 N2명의 순서와 각 학생이 좋아하는 학생이 다음과 같은 경우를 생각해보자.

가장 먼저, 4번 학생의 자리를 정해야 한다. 현재 교실의 모든 칸은 빈 칸이다. 2번 조건에 의해 인접한 칸 중에서 비어있는 칸이 가장 많은 칸인 (2, 2)이 4번 학생의 자리가 된다.

다음 학생은 3번이다. 1번 조건을 만족하는 칸은 (1, 2), (2, 1), (2, 3), (3, 2) 이다. 이 칸은 모두 비어있는 인접한 칸이 2개이다. 따라서, 3번 조건에 의해 (1, 2)가 3번 학생의 자리가 된다.

다음은 9번 학생이다. 9번 학생이 좋아하는 학생의 번호는 8, 1, 2, 3이고, 이 중에 3은 자리에 앉아있다. 좋아하는 학생이 가장 많이 인접한 칸은 (1, 1), (1, 3)이다. 두 칸 모두 비어있는 인접한 칸이 1개이고, 행의 번호도 1이다. 따라서, 3번 조건에 의해 (1, 1)이 9번 학생의 자리가 된다.

이번에 자리를 정할 학생은 8번 학생이다. (2, 1)이 8번 학생이 좋아하는 학생과 가장 많이 인접한 칸이기 때문에, 여기가 그 학생의 자리이다.

7번 학생의 자리를 정해보자. 1번 조건을 만족하는 칸은 (1, 3), (2, 3), (3, 1), (3, 2)로 총 4개가 있고, 비어있는 칸과 가장 많이 인접한 칸은 (2, 3), (3, 2)이다. 행의 번호가 작은 (2, 3)이 7번 학생의 자리가 된다.

이런식으로 학생의 자리를 모두 정하면 다음과 같다.

이제 학생의 만족도를 구해야 한다. 학생의 만족도는 자리 배치가 모두 끝난 후에 구할 수 있다. 학생의 만족도를 구하려면 그 학생과 인접한 칸에 앉은 좋아하는 학생의 수를 구해야 한다. 그 값이 0이면 학생의 만족도는 0, 1이면 1, 2이면 10, 3이면 100, 4이면 1000이다.

학생의 만족도의 총 합을 구해보자.

입력:

첫째 줄에 N이 주어진다. 둘째 줄부터 N2개의 줄에 학생의 번호와 그 학생이 좋아하는 학생 4명의 번호가 한 줄에 하나씩 선생님이 자리를 정할 순서대로 주어진다.

학생의 번호는 중복되지 않으며, 어떤 학생이 좋아하는 학생 4명은 모두 다른 학생으로 이루어져 있다. 입력으로 주어지는 학생의 번호, 좋아하는 학생의 번호는 N2보다 작거나 같은 자연수이다. 어떤 학생이 자기 자신을 좋아하는 경우는 없다.

출력:

첫째 줄에 학생의 만족도의 총 합을 출력한다.

풀이방법:

 문제의 조건에 따라 학생을 배치할 때, 고려해야 하는 점은 '빈칸'과 '친한친구의 수'다.

따라서 각 학생의 번호에 따른 선호도를 dict 형태로 정리한 후 첫 학생들부터 배치하기 시작한다. 학생들을 배치하기 위해 교실을 모두 탐색한다. 탐색한 자리가 빈 자리면 그 자리를 기준으로 빈 자리는 몇명인지, 배치하려고 하는 학생이 선호하는 학생의 수를 파악한다. 각 개수를 모두 세고 나면 조건 1, 2에 따라 좌표를 업데이트 한다. (조건 3은 이중 for로 인해 자동으로 고려된다.)

 모든 학생을 배치하고 난 뒤에는 다시 한 번 교실을 탐색하여 정해진 점수를 부여한다.

문제링크:

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

문제:

어떤 공연장에는 가로로 C개, 세로로 R개의 좌석이 C×R격자형으로 배치되어 있다. 각 좌석의 번호는 해당 격자의 좌표 (x,y)로 표시된다.

예를 들어보자. 아래 그림은 가로 7개, 세로 6개 좌석으로 구성된 7×6격자형 좌석배치를 보여주고 있다. 그림에서 각 단위 사각형은 개별 좌석을 나타내며, 그 안에 표시된 값 (x,y)는 해당 좌석의 번호를 나타낸다. 가장 왼쪽 아래의 좌석번호는 (1,1)이며, 가장 오른쪽 위 좌석의 번호는 (7,6)이다. 

이 공연장에 입장하기 위하여 많은 사람이 대기줄에 서있다. 기다리고 있는 사람들은 제일 앞에서부터 1, 2, 3, 4, . 순으로 대기번호표를 받았다. 우리는 대기번호를 가진 사람들에 대하여 (1,1)위치 좌석부터 시작하여 시계방향으로 돌아가면서 비어있는 좌석에 관객을 순서대로 배정한다. 이것을 좀 더 구체적으로 설명하면 다음과 같다.

먼저 첫 번째 사람, 즉 대기번호 1인 사람은 자리 (1,1)에 배정한다. 그 다음에는 위쪽 방향의 좌석으로 올라가면서 다음 사람들을 배정한다. 만일 더 이상 위쪽 방향으로 빈 좌석이 없으면 오른쪽으로 가면서 배정한다. 오른쪽에 더 이상 빈자리가 없으면 아래쪽으로 내려간다. 그리고 아래쪽에 더 이상 자리가 없으면 왼쪽으로 가면서 남은 빈 좌석을 배정한다. 이 후 왼쪽으로 더 이상의 빈 좌석이 없으면 다시 위쪽으로 배정하고, 이 과정을 모든 좌석이 배정될 때까지 반복한다. 

아래 그림은 7×6공연장에서 대기번호 1번부터 42번까지의 관객이 좌석에 배정된 결과를 보여주고 있다.

여러분은 공연장의 크기를 나타내는 자연수 C와 R이 주어져 있을 때, 대기 순서가 K인 관객에게 배정될 좌석 번호 (x,y)를 찾는 프로그램을 작성해야 한다. 

입력:

첫 줄에는 공연장의 격자 크기를 나타내는 정수 C와 R이 하나의 공백을 사이에 두고 차례대로 주어진다. 두 값의 범위는 5 ≤ C, R ≤ 1,000이다. 그 다음 줄에는 어떤 관객의 대기번호 K가 주어진다. 단 1 ≤ K ≤ 100,000,000이다.

출력:

입력으로 제시된 대기번호 K인 관객에게 배정될 좌석번호 (x,y)를 구해서 두 값, x와 y를 하나의 공백을 사이에 두고 출력해야 한다. 만일 모든 좌석이 배정되어 해당 대기번호의 관객에게 좌석을 배정할 수 없는 경우에는 0(숫자 영)을 출력해야 한다. 

풀이방법:

 이 문제처럼 회전하며 숫자를 할당하는 알고리즘을 달팽이 배열이라고 한다. 생각보다 자주 나오는 알고리즘인 것 같아서 숙지할 필요가 있는 것 같다.

 주어진 공연장에 숫자를 달팽이 배열로 배치한 후 공연장의 값을 모두 탐색하여 K에 해당하는 R, C의 값을 반환하도록 한다.

문제링크:

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

문제:

지민이는 전체 페이지의 수가 N인 책이 하나 있다. 첫 페이지는 1 페이지이고, 마지막 페이지는 N 페이지이다. 각 숫자가 전체 페이지 번호에서 모두 몇 번 나오는지 구해보자.

입력:

첫째 줄에 N이 주어진다. N은 1,000,000,000보다 작거나 같은 자연수이다.

출력:

첫째 줄에 0이 총 몇 번 나오는지, 1이 총 몇 번 나오는지, ..., 9가 총 몇 번 나오는지를 공백으로 구분해 출력한다.

풀이방법:

 0부터 9까지는 각 숫자가 한번씩 나온다는 사실을 사용해서 이 문제를 해결한다.

예를 들어 N이 99로 주어진다면 일의 자리만 보았을 때, 0~9가 총 10번 나타나고, N이 29로 주어진다면 0~9는 총 3번 등장할 것이다. 즉, 십의 자리에 따라서 나오는 횟수가 달라지게 된다.

 일의 자리가 아닌 다른 자릿수도 그와 유사하게 구할 수 있다. 다만 각 자릿수에 따른 배수를 고려해야 한다. 19의 경우 십의 자리만 봤을 때, 10~19까지 1이 총 10번 등장하는 것을 알 수 있다. 즉 각 자릿수에 따라 1배, 10배, 100배, ... 만큼의 갯수가 존재한다고 생각하면 된다.

 0~9의 틀을 고정하기 위해서 매 N의 일의 자리를 9로 고정시켜주도록 한다. N이 121일 때의 예시로 코드가 돌아가는 것을 확인해본다.

우선 121의 일의 자릿수를 9로 만들기 위해 121, 120만 따로 계산해주도록 한다. 이 과정이 끝나면 N=119가 되고, answer는 [1, 3, 2, 0, 0, 0, 0, 0, 0, 0]가 된다.

119에서 일의 자리에서 0~9는 총 12번 나타나게 된다. 따라서 각 answer에 12를 더해주고, 책 페이지의 시작은 1이기 때문에 0의 자릿수만 하나 빼주도록 한다. 이 과정이 끝나면 N=11이 되고, answer는 [12, 15, 14, 12, 12, 12, 12, 12, 12, 12]가 된다.

N = 11이기 때문에 9로 만들어주도록 한다. 11과 10만 따로 계산을 진행하며, 이 때 배수는 10이기 때문에 N=9, answer는 [22, 45, 14, 12, 12, 12, 12, 12, 12, 12]가 된다.

 십의 자리에서 0~9가 총 1*10번 나타나게 된다. 따라서 각 answer에 10을 더해주고, 십의 자리에서 0은 존재할 수 없기 때문에 0의 자릿수만 빼주도록 한다. (01, 02, 03, ... 은 존재하지 않음)

따라서 최종적으로 22 55 24 22 22 22 22 22 22 22 의 값을 가지게 된다.

문제링크:

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

문제:

개똥벌레 한 마리가 장애물(석순과 종유석)로 가득찬 동굴에 들어갔다. 동굴의 길이는 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