CodeDrive

문제:

다음과 같은 규칙에 따라 수들을 만들려고 한다.

1. 첫 번째 수로 양의 정수가 주어진다.
2. 두 번째 수는 양의 정수 중에서 하나를 선택한다.
3. 세 번째부터 이후에 나오는 모든 수는 앞의 앞의 수에서 앞의 수를 빼서 만든다. 예를 들어, 세 번째 수는 첫 번째 수에서 두 번째 수를 뺀 것이고, 네 번째 수는 두 번째 수에서 세 번째 수를 뺀 것이다.
4. 음의 정수가 만들어지면, 이 음의 정수를 버리고 더 이상 수를 만들지 않는다.

첫 번째 수로 100이 주어질 때, 두 번째 수로 60을 선택하여 위의 규칙으로 수들을 만들면 7개의 수들 100, 60, 40, 20, 20 , 0, 20이 만들어진다. 그리고 두 번째 수로 62를 선택하여 위의 규칙으로 수들을 만들면 8개의 수들 100, 62, 38, 24, 14, 10, 4, 6이 만들어진다. 위의 예에서 알 수 있듯이, 첫 번째 수가 같더라도 두 번째 수에 따라서 만들어지는 수들의 개수가 다를 수 있다.

입력으로 첫 번째 수가 주어질 때, 이 수에서 시작하여 위의 규칙으로 만들어지는 최대 개수의 수들을 구하는 프로그램을 작성하시오. 최대 개수의 수들이 여러 개일 때, 그중 하나의 수들만 출력하면 된다.

입력:

첫 번째 수가 주어진다. 이 수는 30,000 보다 같거나 작은 양의 정수이다.

출력:

첫 번째 줄에는 입력된 첫 번째 수로 시작하여 위의 규칙에 따라 만들 수 있는 수들의 최대 개수를 출력한다.

둘째 줄에 그 최대 개수의 수들을 차례대로 출력한다. 이들 수 사이에는 빈칸을 하나씩 둔다.

풀이방법:

 주어질 수 있는 첫 번째 수가 크지 않기 때문에 브루트 포스 방법으로 모든 케이스를 고려하여 해결하면 된다. 1부터 N까지 반복하여 두 번째 수를 결정하고 3번, 4번의 과정을 진행한다. 4번으로 인해 더 이상 수를 만들지 않을 때마다 생성한 수들의 갯수를 비교하여 이전 케이스보다 큰 경우에만 기록하도록 한다.

문제링크:

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

문제:

병현이는 지은이에게 문자 A, B, C, D, E, F, G, H 로 쓰여진 편지를 날마다 보내는데, 컴퓨터로 보내는 비밀편지로, 한 문자마다 0 또는 1인 숫자 여섯 개를 사용하여 보낸다. 둘 사이의 약속은 다음과 같다.

• A 000000
• B 001111
• C 010011
• D 011100
• E 100110
• F 101001
• G 110101
• H 111010

병현이가 어느 날 001111000000011100 을 보내면 지은이는 이것을 BAD로 이해하게 된다. 그런데 둘 사이에 약속이 잘 만들어져 있기 때문에, 통신에 문제가 생겨서 한 문자를 표시하는 여섯 숫자 중 어느 한 숫자만 틀리게 오는 경우, 지은이는 원래 보내려는 문자를 알아 낼 수가 있다.

예를 들어 지은이가 000100을 받았을 때, A와 숫자 한자만 다르고, 다른 문자들과는 각각 숫자 두 자 이상이 다르므로 지은이는 이것이 A라고 알아보게 된다.

다만 111111과 같이 모든 문자의 표현과 숫자 두 자 이상이 다른 경우에는 무슨 문자인지 알 수가 없게 된다. 예를 들어 지은이가 011111000000111111000000111111 을 받았을 때, BA 다음에 알아 볼 수 없는 문자가 나오는데. 이 경우 이런 것이 처음 나오는 문자의 위치인 3을 출력한다.

지은이가 받은 편지를 보고 문자들을 알아내어 출력하거나, 모르는 문자가 있는 경우, 이것이 처음 나오는 위치를 출력하는 프로그램을 작성하시오.

입력:

첫줄에는 보낸 문자의 개수(10개 보다 작다.)가 입력된다. 다음 줄에는 문자의 개수의 여섯 배 만큼의 숫자 입력이 주어진다.

출력:

주어진 입력에서 지은이가 이해한 문자들을 출력하거나, 모르는 문자가 나오는 경우 그런 것이 처음 나오는 위치를 출력한다.

풀이방법:

 단순히 문자열을 한자리씩 비교하며 하는 방식이 아니라 비트연산을 사용한 방법을 사용했다. 우선 알파벳별로 정해진 값들은 0 또는 1인 숫자 여섯 개이기 때문에 이를 이진수라고 생각한다. 따라서 입력받은 문자열을 6자리씩 잘라서 XOR 연산을 통해서 찾도록 한다.

 자른 문자열이 alpha에 있다면 바로 더해주고, 없다면 alpha의 key를 순회하면서 XOR 연산값이 1이 있다면 그 key를 잘못 보낸 것이기 때문에 해당 key의 value 값을 더해주도록 한다.

문제링크:

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

문제:

오목은 바둑판에 검은 바둑알과 흰 바둑알을 교대로 놓아서 겨루는 게임이다. 바둑판에는 19개의 가로줄과 19개의 세로줄이 그려져 있는데 가로줄은 위에서부터 아래로 1번, 2번, ... ,19번의 번호가 붙고 세로줄은 왼쪽에서부터 오른쪽으로 1번, 2번, ... 19번의 번호가 붙는다.

위의 그림에서와 같이 같은 색의 바둑알이 연속적으로 다섯 알을 놓이면 그 색이 이기게 된다. 여기서 연속적이란 가로, 세로 또는 대각선 방향 모두를 뜻한다. 즉, 위의 그림은 검은색이 이긴 경우이다. 하지만 여섯 알 이상이 연속적으로 놓인 경우에는 이긴 것이 아니다.

입력으로 바둑판의 어떤 상태가 주어졌을 때, 검은색이 이겼는지, 흰색이 이겼는지 또는 아직 승부가 결정되지 않았는지를 판단하는 프로그램을 작성하시오. 단, 검은색과 흰색이 동시에 이기거나 검은색 또는 흰색이 두 군데 이상에서 동시에 이기는 경우는 입력으로 들어오지 않는다.

입력:

19줄에 각 줄마다 19개의 숫자로 표현되는데, 검은 바둑알은 1, 흰 바둑알은 2, 알이 놓이지 않는 자리는 0으로 표시되며, 숫자는 한 칸씩 띄어서 표시된다.

출력:

첫줄에 검은색이 이겼을 경우에는 1을, 흰색이 이겼을 경우에는 2를, 아직 승부가 결정되지 않았을 경우에는 0을 출력한다. 검은색 또는 흰색이 이겼을 경우에는 둘째 줄에 연속된 다섯 개의 바둑알 중에서 가장 왼쪽에 있는 바둑알(연속된 다섯 개의 바둑알이 세로로 놓인 경우, 그 중 가장 위에 있는 것)의 가로줄 번호와, 세로줄 번호를 순서대로 출력한다.

풀이방법:

 이 문제는 오목인지는 판정한 뒤에 육목에 해당하는지에 판단 여부가 중요한 문제다. 우선 19x19의 모든 점에서 흰돌이나 검은돌이 있다면 오목인지 판정을 시작한다. 오목을 판정하는 방법은 해당 점으로 부터 8 방향으로 움직이며 돌이 연속되는지 판단하도록 한다. 기준점으로부터 연속하여 4개가 더 있다면 우선 오목이라고 판정한다. 그리고 한 번 더 해당 방향으로 이동하고, 처음 기준점에서 움직였던 반대 방향(180도 반대)으로 한 칸씩 움직여서 육목의 여부 판정을 더 수행한다. 정확한 오목이라면 값을 반환하고 저장하도록 한다.

 동시에 이기는 경우는 없기 때문에 값을 가지고 있는 리스트의 인덱스가 정답에 해당하며, 조건에 맞게(가장 왼쪽에 있는 바둑알) 출력하도록 한다. 만약 둘 다 비어 있다면 아직 승부가 결정되지 않은 경우이므로 0을 출력한다.

문제링크:

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

문제:

아래 <그림 1>과 같이 직사각형 모양의 종이가 있다. 이 종이는 가로방향과 세로 방향으로 1㎝마다 점선이 그어져 있다. 가로 점선은 위에서 아래로 1번부터 차례로 번호가 붙어 있고, 세로 점선은 왼쪽에서 오른쪽으로 번호가 붙어 있다.

<그림 1>

점선을 따라 이 종이를 칼로 자르려고 한다. 가로 점선을 따라 자르는 경우는 종이의 왼쪽 끝에서 오른쪽 끝까지, 세로 점선인 경우는 위쪽 끝에서 아래쪽 끝까지 한 번에 자른다. 예를 들어, <그림 1>의 가로 길이 10㎝이고 세로 길이 8㎝인 종이를 3번 가로 점선, 4번 세로 점선, 그리고 2번 가로 점선을 따라 자르면 <그림 2>와 같이 여러 개의 종이 조각으로 나뉘게 된다. 이때 가장 큰 종이 조각의 넓이는 30㎠이다.

<그림 2>

입력으로 종이의 가로 세로 길이, 그리고 잘라야할 점선들이 주어질 때, 가장 큰 종이 조각의 넓이가 몇 ㎠인지를 구하는 프로그램을 작성하시오.

입력:

첫줄에는 종이의 가로와 세로의 길이가 차례로 자연수로 주어진다. 가로와 세로의 길이는 최대 100㎝이다. 둘째 줄에는 칼로 잘라야하는 점선의 개수가 주어진다. 셋째 줄부터 마지막 줄까지 한 줄에 점선이 하나씩 아래와 같은 방법으로 입력된다. 가로로 자르는 점선은 0과 점선 번호가 차례로 주어지고, 세로로 자르는 점선은 1과 점선 번호가 주어진다. 입력되는 두 숫자 사이에는 빈 칸이 하나씩 있다.

출력:

첫째 줄에 가장 큰 종이 조각의 넓이를 출력한다. 단, 넓이의 단위는 출력하지 않는다.

풀이방법:

 입력으로 받은 잘라야 하는 순서를 오름차순으로 정렬한 뒤, 이전 값과의 차이를 구하며 모든 종이 조각의 넓이를 구하고 가장 큰 종이 조각을 출력하면 된다.

문제링크:

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

문제:

송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다. 맥주 한 박스에는 맥주가 20개 들어있다. 목이 마르면 안되기 때문에 50미터에 한 병씩 마시려고 한다. 즉, 50미터를 가려면 그 직전에 맥주 한 병을 마셔야 한다.

상근이의 집에서 페스티벌이 열리는 곳은 매우 먼 거리이다. 따라서, 맥주를 더 구매해야 할 수도 있다. 미리 인터넷으로 조사를 해보니 다행히도 맥주를 파는 편의점이 있다. 편의점에 들렸을 때, 빈 병은 버리고 새 맥주 병을 살 수 있다. 하지만, 박스에 들어있는 맥주는 20병을 넘을 수 없다. 편의점을 나선 직후에도 50미터를 가기 전에 맥주 한 병을 마셔야 한다.

편의점, 상근이네 집, 펜타포트 락 페스티벌의 좌표가 주어진다. 상근이와 친구들이 행복하게 페스티벌에 도착할 수 있는지 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 테스트 케이스의 개수 t가 주어진다. (t ≤ 50)

각 테스트 케이스의 첫째 줄에는 맥주를 파는 편의점의 개수 n이 주어진다. (0 ≤ n ≤ 100).

다음 n+2개 줄에는 상근이네 집, 편의점, 펜타포트 락 페스티벌 좌표가 주어진다. 각 좌표는 두 정수 x와 y로 이루어져 있다. (두 값 모두 미터, -32768 ≤ x, y ≤ 32767)

송도는 직사각형 모양으로 생긴 도시이다. 두 좌표 사이의 거리는 x 좌표의 차이 + y 좌표의 차이 이다. (맨해튼 거리)

출력:

각 테스트 케이스에 대해서 상근이와 친구들이 행복하게 페스티벌에 갈 수 있으면 "happy", 중간에 맥주가 바닥나서 더 이동할 수 없으면 "sad"를 출력한다. 

풀이방법:

 맥주 한 박스에는 맥주가 20개 들어있고, 편의점에서 이를 채울 수 있다. 편의점에 도달하면 무조건 맥주를 가득 채우는 것이 이득이므로, 최대로 이동할 수 있는 거리는 1000미터다. 따라서 현재 있는 위치로부터 1000미터 이내에 편의점이 있거나 페스티벌을 하는 장소가 있는지 찾으면 된다. 

 따라서 페스티벌을 하는 장소에 도달하는지의 여부를 찾으면 되기 때문에 1000미터 이내에 도달할 수 있는 장소를 모두 저장하며 탐색하는 BFS 방법을 사용하도록 한다.

문제링크:

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

문제:

다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있다. 다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 한다. 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모두 뒤집는 것이다. 뒤집는 것은 1을 0으로, 0을 1로 바꾸는 것을 의미한다.

예를 들어 S=0001100 일 때,

1. 전체를 뒤집으면 1110011이 된다.
2. 4번째 문자부터 5번째 문자까지 뒤집으면 1111111이 되어서 2번 만에 모두 같은 숫자로 만들 수 있다.

하지만, 처음부터 4번째 문자부터 5번째 문자까지 문자를 뒤집으면 한 번에 0000000이 되어서 1번 만에 모두 같은 숫자로 만들 수 있다.

문자열 S가 주어졌을 때, 다솜이가 해야하는 행동의 최소 횟수를 출력하시오.

입력:

첫째 줄에 문자열 S가 주어진다. S의 길이는 100만보다 작다.

출력:

첫째 줄에 다솜이가 해야하는 행동의 최소 횟수를 출력한다.

풀이방법:

 앞에서부터 하나씩 비교해보면서 숫자가 달라지는 횟수를 측정하고 더 작은 변경으로 선택하면 된다. 비교를 할 때, 길이-1의 값까지만 측정했기 때문에 맨 마지막 값의 count도 더해주도록 한다. 만약 하지 않는다면, 10010과 같은 케이스일 때, 오류가 발생할 수 있다.

문제링크:

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

문제:

수빈이가 세상에서 가장 좋아하는 것은 소수이고, 취미는 소수를 가지고 노는 것이다. 요즘 수빈이가 가장 관심있어 하는 소수는 7331이다.

7331은 소수인데, 신기하게도 733도 소수이고, 73도 소수이고, 7도 소수이다. 즉, 왼쪽부터 1자리, 2자리, 3자리, 4자리 수 모두 소수이다! 수빈이는 이런 숫자를 신기한 소수라고 이름 붙였다.

수빈이는 N자리의 숫자 중에서 어떤 수들이 신기한 소수인지 궁금해졌다. N이 주어졌을 때, 수빈이를 위해 N자리 신기한 소수를 모두 찾아보자.

입력:

첫째 줄에 N(1 ≤ N ≤ 8)이 주어진다.

출력:

N자리 수 중에서 신기한 소수를 오름차순으로 정렬해서 한 줄에 하나씩 출력한다.

풀이방법:

 보통 일반적인 소수 문제의 경우에는 에라토스테네스의 체를 사용해서 소수인 수들을 모두 찾고 하는 것이 빠른 경우가 많으나, 이 문제의 경우에는 N = 8 인 경우에 수가 엄청 커지게 되고, 시간이 오래 걸리게 된다.

 따라서 이 문제의 경우에는 dfs를 사용해서 한자리씩 붙여 나가면서 소수를 판정하는 방식을 사용하도록 한다. 문제의 특징으로 인해 75가 소수가 아니므로, 그 뒤는 판정할 필요가 없기 때문이다. dfs의 종료 조건은 숫자의 길이가 N이 될 때까지 진행한다.

문제링크:

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

문제:

지민이는 N개의 물병을 가지고 있다. 각 물병에는 물을 무한대로 부을 수 있다. 처음에 모든 물병에는 물이 1리터씩 들어있다. 지민이는 이 물병을 또 다른 장소로 옮기려고 한다. 지민이는 한 번에 K개의 물병을 옮길 수 있다. 하지만, 지민이는 물을 낭비하기는 싫고, 이동을 한 번보다 많이 하기는 싫다. 따라서, 지민이는 물병의 물을 적절히 재분배해서, K개를 넘지 않는 비어있지 않은 물병을 만들려고 한다.

물은 다음과 같이 재분배 한다.

먼저 같은 양의 물이 들어있는 물병 두 개를 고른다. 그 다음에 한 개의 물병에 다른 한 쪽에 있는 물을 모두 붓는다. 이 방법을 필요한 만큼 계속 한다.

이런 제약 때문에, N개로 K개를 넘지않는 비어있지 않은 물병을 만드는 것이 불가능할 수도 있다. 다행히도, 새로운 물병을 살 수 있다. 상점에서 사는 물병은 물이 1리터 들어있다.

예를 들어, N=3이고, K=1일 때를 보면, 물병 3개로 1개를 만드는 것이 불가능하다. 한 병을 또다른 병에 부으면, 2리터가 들어있는 물병 하나와, 1리터가 들어있는 물병 하나가 남는다. 만약 상점에서 한 개의 물병을 산다면, 2리터가 들어있는 물병 두 개를 만들 수 있고, 마지막으로 4리터가 들어있는 물병 한 개를 만들 수 있다.

입력:

첫째 줄에 N과 K가 주어진다. N은 107보다 작거나 같은 자연수이고, K는 1,000보다 작거나 같은 자연수이다.

출력:

첫째 줄에 상점에서 사야하는 물병의 최솟값을 출력한다. 만약 정답이 없을 경우에는 -1을 출력한다.

풀이방법:

 처음에 모든 물병에 물이 1리터씩 들어있고, 이를 한 물병에 합치는 과정을 하는 과정은 이진수를 더하는 것과 같다. 예를 들어, N=3, K=1일 때를 보면, 물병이 3개가 있다는 것은 이진수로 보면 11(3)과 같고, 실제로 2리터가 들어있는 물병 하나와, 1리터가 들어있는 물병 하나가 남아있다. 만약 상점에서 한 개의 물병을 산다면, 4리터가 들어있는 물병 한 개를 만들 수 있다. (11+1 =100) 

 즉, 이 문제는 주어진 N을 2진수로 변경한 뒤에 1씩 더하면서, 더한 값의 이진수 값에 1의 값이 K개 있을 때까지 반복하여 더해주면 된다.

문제링크:

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

문제:

어린 왕자는 소혹성 B-664에서 자신이 사랑하는 한 송이 장미를 위해 살아간다. 어느 날 장미가 위험에 빠지게 된 것을 알게 된 어린 왕자는, 장미를 구하기 위해 은하수를 따라 긴 여행을 하기 시작했다. 하지만 어린 왕자의 우주선은 그렇게 좋지 않아서 행성계 간의 이동을 최대한 피해서 여행해야 한다. 아래의 그림은 어린 왕자가 펼쳐본 은하수 지도의 일부이다.

빨간 실선은 어린 왕자가 출발점에서 도착점까지 도달하는데 있어서 필요한 행성계 진입/이탈 횟수를 최소화하는 경로이며, 원은 행성계의 경계를 의미한다. 이러한 경로는 여러 개 존재할 수 있지만 적어도 3번의 행성계 진입/이탈이 필요하다는 것을 알 수 있다.

위와 같은 은하수 지도, 출발점, 도착점이 주어졌을 때 어린 왕자에게 필요한 최소의 행성계 진입/이탈 횟수를 구하는 프로그램을 작성해 보자. 행성계의 경계가 맞닿거나 서로 교차하는 경우는 없다. 또한, 출발점이나 도착점이 행성계 경계에 걸쳐진 경우 역시 입력으로 주어지지 않는다.

입력:

입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 첫째 줄에 출발점 (x1, y1)과 도착점 (x2, y2)이 주어진다. 두 번째 줄에는 행성계의 개수 n이 주어지며, 세 번째 줄부터 n줄에 걸쳐 행성계의 중점과 반지름 (cx, cy, r)이 주어진다.

출력:

각 테스트 케이스에 대해 어린 왕자가 거쳐야 할 최소의 행성계 진입/이탈 횟수를 출력한다.

풀이방법:

 시작점, 도착점과 입력으로 들어온 원의 중심과 거리를 비교하여 원 안에 있는지 밖에 있는지 확인한다. 원의 반지름과 각 거리를 비교했을 때, 각 경우의 수는 다음을 의미한다.

• 각 거리들이 반지름 r보다 클 때, 원의 밖에 있는 것을 의미하고, 반지름 r 보다 작다면, 원의 안에 있는 것을 의미한다.
  • 따라서 둘 다 밖에 있거나 안에 있다면 행성계 진입/이탈이 필요하지 않다.
  • 둘 중 한 거리만 안에 있다면 이 때는 행성계 진입/이탈이 필요하므로 이 경우의 수에 대해서만 count 한다.

문제링크:

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

문제:

N명의 학생들을 키 순서대로 줄을 세우려고 한다. 각 학생의 키를 직접 재서 정렬하면 간단하겠지만, 마땅한 방법이 없어서 두 학생의 키를 비교하는 방법을 사용하기로 하였다. 그나마도 모든 학생들을 다 비교해 본 것이 아니고, 일부 학생들의 키만을 비교해 보았다.

일부 학생들의 키를 비교한 결과가 주어졌을 때, 줄을 세우는 프로그램을 작성하시오.

입력:

첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의미이다.

학생들의 번호는 1번부터 N번이다.

출력:

첫째 줄에 학생들을 키 순서대로 줄을 세운 결과를 출력한다. 답이 여러 가지인 경우에는 아무거나 출력한다.

풀이방법:

 사이클이 존재하지 않고, 방향이 존재하는 그래프 상에서의 정렬을 해야 하는 문제이기 때문에 위상정렬을 사용해서 이 문제를 푼다. 

 위상정렬의 기본 알고리즘 진행은 다음과 같다.

1. 각 입력으로 들어온 값들을 그래프 형태로 저장한다. 이와 동시에 in_degree라는 간선이 연결된 갯수를 저장하는 배열도 같이 초기화 시킨다.

2. 모든 입력을 마친 뒤, in_degree가 0인 것부터 queue(deque)에 입력해 준다.

3. queue에서 값을 하나씩 빼면서 나온 노드들이 정렬된 것이며, 해당 노드와 연결되어 있는 선을 하나씩 제거한다.

3-1. 이 때, in_degree 값이 0이 된다면 queue에 넣는다.

4. 위 과정을 queue가 비어 있을 때까지 한다.

문제링크:

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