CodeDrive

문제:

김지민은 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

문제:

보물섬 지도를 발견한 후크 선장은 보물을 찾아나섰다. 보물섬 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 각 칸은 육지(L)나 바다(W)로 표시되어 있다. 이 지도에서 이동은 상하좌우로 이웃한 육지로만 가능하며, 한 칸 이동하는데 한 시간이 걸린다. 보물은 서로 간에 최단 거리로 이동하는데 있어 가장 긴 시간이 걸리는 육지 두 곳에 나뉘어 묻혀있다. 육지를 나타내는 두 곳 사이를 최단 거리로 이동하려면 같은 곳을 두 번 이상 지나가거나, 멀리 돌아가서는 안 된다.

예를 들어 위와 같이 지도가 주어졌다면 보물은 아래 표시된 두 곳에 묻혀 있게 되고, 이 둘 사이의 최단 거리로 이동하는 시간은 8시간이 된다.

보물 지도가 주어질 때, 보물이 묻혀 있는 두 곳 간의 최단 거리로 이동하는 시간을 구하는 프로그램을 작성하시오.

입력:

첫째 줄에는 보물 지도의 세로의 크기와 가로의 크기가 빈칸을 사이에 두고 주어진다. 이어 L과 W로 표시된 보물 지도가 아래의 예와 같이 주어지며, 각 문자 사이에는 빈 칸이 없다. 보물 지도의 가로, 세로의 크기는 각각 50이하이다.

출력:

첫째 줄에 보물이 묻혀 있는 두 곳 사이를 최단 거리로 이동하는 시간을 출력한다.

풀이방법:

for(bfs) 방법을 사용해야 하는 방법으로 시간이 많이 필요한 문제라 생각했고, pypy3으로 통과했다. 지도의 모든 L에 대해서 bfs를 수행한다. 각 bfs에서는 해당 L로부터 가장 멀리 갈 수 있는 거리를 찾는다.

문제링크:

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

문제:

남극에 사는 김지민 선생님은 학생들이 되도록이면 많은 단어를 읽을 수 있도록 하려고 한다. 그러나 지구온난화로 인해 얼음이 녹아서 곧 학교가 무너지기 때문에, 김지민은 K개의 글자를 가르칠 시간 밖에 없다. 김지민이 가르치고 난 후에는, 학생들은 그 K개의 글자로만 이루어진 단어만을 읽을 수 있다. 김지민은 어떤 K개의 글자를 가르쳐야 학생들이 읽을 수 있는 단어의 개수가 최대가 되는지 고민에 빠졌다.

남극언어의 모든 단어는 "anta"로 시작되고, "tica"로 끝난다. 남극언어에 단어는 N개 밖에 없다고 가정한다. 학생들이 읽을 수 있는 단어의 최댓값을 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문자로만 이루어져 있고, 길이가 8보다 크거나 같고, 15보다 작거나 같다. 모든 단어는 중복되지 않는다.

출력:

첫째 줄에 김지민이 K개의 글자를 가르칠 때, 학생들이 읽을 수 있는 단어 개수의 최댓값을 출력한다.

풀이방법:

 일반적인 브루트포스 방법을 사용하면 시간초과가 날 수 있기 때문에, 비트마스킹이라는 방법을 사용했다. "anta", "tica"에서 사용되는 "a","n","t","i","c"를 제외하고 나머지 알파벳에 대해서 20개의 비트가 있다고 가정하고, 사용하면 1을 올리고, 사용하지 않으면 0으로 냅두는 방법을 사용한다. 

 항상 5개의 알파벳은 사용해야 하기 때문에, k가 5보다 작으면 읽을 수 있는 단어가 없다. 이외의 경우에는 가능한 알파벳에서 k-5개의 알파벳을 뽑은 뒤(가능한 모든 조합에 대해), 비트마스킹을 통해 갯수를 세고, 그 중 최댓값을 반환하도록 한다.

문제링크:

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

문제:

페르마의 마지막 정리는, a, b, c가 0이 아닌 정수이고, n이 2보다 큰 자연수 일 때, an = bn + cn을 만족하는 자연수 a, b, c가 존재하지 않는다는 정리이다. 이 정리는 아직 증명되지 않았다.

하지만, 완전 세제곱 방정식 a3 = b3 + c3 + d3을 만족하는 1보다 큰 자연수를 찾는 것은 어렵지 않다. (123 = 63 + 83 + 103)

이러한 완전 세제곱 방정식과 a ≤ 100을 만족하는 {a, b, c, d}쌍을 모두 찾는 프로그램을 작성하시오.

입력:

이 문제는 입력이 없다.

출력:

a값이 증가하는 순서대로 아래 출력 형식과 같이 출력한다. b, c, d도 증가하는 순서로 이루어져야 한다. a값에 해당하는 b, c, d쌍이 여러 개 존재할 수 있다. 이때는 b 값이 작은 것부터 먼저 출력한다.

아래 출력 예제는 일부분만 나와있다.

풀이방법:

 조건이 맞는 a,b,c,d를 찾는 것은 쉬우나 시간을 줄이는 것이 이 문제의 핵심이다. a 같은 경우에는 6이 가장 같은 경우의 수 이기 때문에 6부터 시작하게 한다. 그리고 1보다 큰 자연수여야 하기 때문에 b는 2부터, b<c<d를 만족해야하기 때문에 c는 b부터, d는 c부터 시작하게 하도록 한다.

문제링크:

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

문제:

크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸, 왼쪽에서부터 c번째 칸을 의미한다. r과 c는 1부터 시작한다.

이 도시에 사는 사람들은 치킨을 매우 좋아한다. 따라서, 사람들은 "치킨 거리"라는 말을 주로 사용한다. 치킨 거리는 집과 가장 가까운 치킨집 사이의 거리이다. 즉, 치킨 거리는 집을 기준으로 정해지며, 각각의 집은 치킨 거리를 가지고 있다. 도시의 치킨 거리는 모든 집의 치킨 거리의 합이다.

임의의 두 칸 (r1, c1)과 (r2, c2) 사이의 거리는 |r1-r2| + |c1-c2|로 구한다.

예를 들어, 아래와 같은 지도를 갖는 도시를 살펴보자.

0은 빈 칸, 1은 집, 2는 치킨집이다.

(2, 1)에 있는 집과 (1, 2)에 있는 치킨집과의 거리는 |2-1| + |1-2| = 2, (5, 5)에 있는 치킨집과의 거리는 |2-5| + |1-5| = 7이다. 따라서, (2, 1)에 있는 집의 치킨 거리는 2이다.

(5, 4)에 있는 집과 (1, 2)에 있는 치킨집과의 거리는 |5-1| + |4-2| = 6, (5, 5)에 있는 치킨집과의 거리는 |5-5| + |4-5| = 1이다. 따라서, (5, 4)에 있는 집의 치킨 거리는 1이다.

이 도시에 있는 치킨집은 모두 같은 프랜차이즈이다. 프렌차이즈 본사에서는 수익을 증가시키기 위해 일부 치킨집을 폐업시키려고 한다. 오랜 연구 끝에 이 도시에서 가장 수익을 많이 낼 수 있는  치킨집의 개수는 최대 M개라는 사실을 알아내었다.

도시에 있는 치킨집 중에서 최대 M개를 고르고, 나머지 치킨집은 모두 폐업시켜야 한다. 어떻게 고르면, 도시의 치킨 거리가 가장 작게 될지 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 N(2 ≤ N ≤ 50)과 M(1 ≤ M ≤ 13)이 주어진다.

둘째 줄부터 N개의 줄에는 도시의 정보가 주어진다.

도시의 정보는 0, 1, 2로 이루어져 있고, 0은 빈 칸, 1은 집, 2는 치킨집을 의미한다. 집의 개수는 2N개를 넘지 않으며, 적어도 1개는 존재한다. 치킨집의 개수는 M보다 크거나 같고, 13보다 작거나 같다.

출력:

첫째 줄에 폐업시키지 않을 치킨집을 최대 M개를 골랐을 때, 도시의 치킨 거리의 최솟값을 출력한다.

풀이방법:

 치킨집들 중에서 임의의 M개의 치킨집을 골라 폐업시킨 뒤, 도시의 치킨 거리를 구한다. 그리고 이 과정을 가능한 모든 조합에 대해서 수행하고, 그 중 가장 최솟값인 도시의 치킨 거리를 출력한다.

 처음 입력을 받을 때 치킨집과 집과의 치킨 거리를 계산을 하고, itertools를 사용해 모든 폐업 조합(남아 있는 집)을 구한다. 남아 있는 집에 대해서 사전에 구했던 치킨 거리들을 합산함으로써 답을 얻는다.

문제링크:

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

문제:

N개의 수로 이루어진 수열 A1, A2, ..., AN이 주어진다. 또, 수와 수 사이에 끼워넣을 수 있는 N-1개의 연산자가 주어진다. 연산자는 덧셈(+), 뺄셈(-), 곱셈(×), 나눗셈(÷)으로만 이루어져 있다.

우리는 수와 수 사이에 연산자를 하나씩 넣어서, 수식을 하나 만들 수 있다. 이때, 주어진 수의 순서를 바꾸면 안 된다.

예를 들어, 6개의 수로 이루어진 수열이 1, 2, 3, 4, 5, 6이고, 주어진 연산자가 덧셈(+) 2개, 뺄셈(-) 1개, 곱셈(×) 1개, 나눗셈(÷) 1개인 경우에는 총 60가지의 식을 만들 수 있다. 예를 들어, 아래와 같은 식을 만들 수 있다.

• 1+2+3-4×5÷6
• 1÷2+3+4-5×6
• 1+2÷3×4-5+6
• 1÷2×3-4+5+6

식의 계산은 연산자 우선 순위를 무시하고 앞에서부터 진행해야 한다. 또, 나눗셈은 정수 나눗셈으로 몫만 취한다. 음수를 양수로 나눌 때는 C++14의 기준을 따른다. 즉, 양수로 바꾼 뒤 몫을 취하고, 그 몫을 음수로 바꾼 것과 같다. 이에 따라서, 위의 식 4개의 결과를 계산해보면 아래와 같다.

• 1+2+3-4×5÷6 = 1
• 1÷2+3+4-5×6 = 12
• 1+2÷3×4-5+6 = 5
• 1÷2×3-4+5+6 = 7

N개의 수와 N-1개의 연산자가 주어졌을 때, 만들 수 있는 식의 결과가 최대인 것과 최소인 것을 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, 곱셈(×)의 개수, 나눗셈(÷)의 개수이다. 

출력:

첫째 줄에 만들 수 있는 식의 결과의 최댓값을, 둘째 줄에는 최솟값을 출력한다. 연산자를 어떻게 끼워넣어도 항상 -10억보다 크거나 같고, 10억보다 작거나 같은 결과가 나오는 입력만 주어진다. 또한, 앞에서부터 계산했을 때, 중간에 계산되는 식의 결과도 항상 -10억보다 크거나 같고, 10억보다 작거나 같다.

풀이방법:

***pypy3으로 통과한 문제입니다.***

 브루트포스 알고리즘을 이용하기 위해 itertools의 permutation을 사용해서 모든 경우의 수를 만들어준다. 만들어진 경우의 수에 따라 조건문으로 알맞게 계산하면 된다. 단, 음수에 대한 나눗셈은 정해진 기준에 맞게 계산되도록 해준다.

문제링크:

www.acmicpc.net/problem/14888

문제:

두 종류의 부등호 기호 ‘<’와 ‘>’가 k개 나열된 순서열  A가 있다. 우리는 이 부등호 기호 앞뒤에 서로 다른 한 자릿수 숫자를 넣어서 모든 부등호 관계를 만족시키려고 한다. 예를 들어, 제시된 부등호 순서열 A가 다음과 같다고 하자.

A =>  < < < > < < > < >

부등호 기호 앞뒤에 넣을 수 있는 숫자는 0부터 9까지의 정수이며 선택된 숫자는 모두 달라야 한다. 아래는 부등호 순서열 A를 만족시키는 한 예이다. 

3 < 4 < 5 < 6 > 1 < 2 < 8 > 7 < 9 > 0

이 상황에서 부등호 기호를 제거한 뒤, 숫자를 모두 붙이면 하나의 수를 만들 수 있는데 이 수를 주어진 부등호 관계를 만족시키는 정수라고 한다. 그런데 주어진 부등호 관계를 만족하는 정수는 하나 이상 존재한다. 예를 들어 3456128790 뿐만 아니라 5689023174도 아래와 같이 부등호 관계 A를 만족시킨다. 

5 < 6 < 8 < 9 > 0 < 2 < 3 > 1 < 7 > 4

여러분은 제시된 k개의 부등호 순서를 만족하는 (k+1)자리의 정수 중에서 최댓값과 최솟값을 찾아야 한다. 앞서 설명한 대로 각 부등호의 앞뒤에 들어가는 숫자는 { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }중에서 선택해야 하며 선택된 숫자는 모두 달라야 한다. 

입력:

첫 줄에 부등호 문자의 개수를 나타내는 정수 k가 주어진다. 그 다음 줄에는 k개의 부등호 기호가 하나의 공백을 두고 한 줄에 모두 제시된다. k의 범위는 2 ≤ k ≤ 9 이다. 

출력:

여러분은 제시된 부등호 관계를 만족하는 k+1 자리의 최대, 최소 정수를 첫째 줄과 둘째 줄에 각각 출력해야 한다. 단 아래 예(1)과 같이 첫 자리가 0인 경우도 정수에 포함되어야 한다. 모든 입력에 답은 항상 존재하며 출력 정수는 하나의 문자열이 되도록 해야 한다. 

풀이방법:

 처음에는 itertools의 permutation을 사용해서 풀려고 했으나, 메모리 초과가 발생했다. 아무래도 경우의 수가 엄청 많기 때문에 발생한 것 같았다.

 따라서 백트래킹(dfs)를 사용해서 효율적으로 구하려고 했다. visited 배열을 만들어서 사용한 숫자, 그렇지 않은 숫자를 구분했고, 빈 문자열로 시작했기 때문에 length==0이라는 조건을 넣어주게 되었다. is_possible 함수를 통해 부등호를 만족하는 조건의 숫자들을 구했으면 이를 answer 배열에 넣도록 한다. 

 이 때, answer 배열들의 숫자들은 작은 숫자부터 생성하기 시작했기 때문에 맨 처음에는 "부등호를 만족하는 가장 작은 숫자", 맨 마지막에는 "부등호를 만족하는 가장 큰 숫자"가 들어가 있게 된다. 따라서 이를 알맞게 출력하면 된다.

문제링크:

www.acmicpc.net/problem/2529

문제:

은민이는 4와 7을 좋아하고, 나머지 숫자는 싫어한다. 금민수는 어떤 수가 4와 7로만 이루어진 수를 말한다.

A와 B가 주어졌을 때, A보다 크거나 같고, B보다 작거나 같은 자연수 중에 금민수인 것의 개수를 출력하는 프로그램을 작성하시오.

입력:

첫째 줄에 A와 B가 주어진다. A는 1보다 크거나 같고, 1,000,000,000보다 작거나 같은 자연수이다. B는 A보다 크거나 같고, 1,000,000,000보다 작거나 같은 자연수이다.

출력:

첫째 줄에 A보다 크거나 같고, B보다 작거나 같은 자연수 중에 금민수인 것의 개수를 출력한다.

풀이방법:

 주어진 수가 1,000,000,000로 엄청 크게 주어졌기 때문에 A~B 사이의 수가 4와 7로 이루어져있는지 탐색하는 것은 시간초과가 발생할 것이다. 따라서4와 7로 구성된 숫자를 만들면서 이 숫자가 A~B 사이에 있는지 확인하도록 한다.

 A와 B가 큰 수로 주어질 수도 있기 때문에 깊이라는 개념을 사용해서 최대한 탐색할 수 있도록 했다. 깊이는 상한값으로 인해 최대 9까지 가능하다. 깊이라는 개념이 추가되었기 때문에 깊이우선탐색을 사용해서 값을 만들어내도록 한다.

 생성된 값이 주어진 범위 안에 들어 있으면 count를 1 올려주고 상한 값을 넘어가면 더 빠른 탐색을 위해서 0을 반환하도록 했다. 하한값에 보다 작은 값에 대해서는 조건이 없는데, 그 이유는 앞서 말했던 A와 B가 큰 수로 주어졌을 때, 그 범위 내까지는 이동하도록 하기 위함이다.

문제링크:

www.acmicpc.net/problem/1527

문제:

어떤 수와 그 수의 숫자 순서를 뒤집은 수가 일치하는 수를 팰린드롬이라 부른다. 예를 들어 79,197과 324,423 등이 팰린드롬 수이다.

어떤 수 N (1 ≤ N ≤ 1,000,000)이 주어졌을 때, N보다 크거나 같고, 소수이면서 팰린드롬인 수 중에서, 가장 작은 수를 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 N이 주어진다.

출력:

첫째 줄에 조건을 만족하는 수를 출력한다.

풀이방법:

 소수를 판정하는 알고리즘 중 에라토느테네스의 체와 팰린드롬 알고리즘을 함께 사용하는 알고리즘이다. N으로 들어올 수 있는 가장 큰 숫자인 1,000,000에 해당하는 답은 1003001이라는 사실을 사용해서 그 만큼을 sosu 리스트를 초기화했다. (혹은 넉넉하게 큰 길이로 초기화해도 된다.) 이 sosu 리스트를 에라토스테네스의 체를 사용해서 소수만 남겨둔다.

 이후 while 반복문을 통해서 sosu이면서 팰린드롬인 경우에 그 숫자를 출력하고 break를 통해 정지시키면 된다.

문제링크:

www.acmicpc.net/problem/1747

문제:

2048 게임은 4x4 크기의 보드에서 혼자 즐기는 게임이다. 

이 게임에서 한 번의 이동은 보드 위에 있는 전체 블록을 상하좌우 네 방향 중 하나로 이동시키는 것이다. 이때, 같은 값을 갖는 두 블록이 충돌하면 두 블록은 하나로 합쳐지게 된다. 한 번의 이동에서 이미 합쳐진 블록은 또 다른 블록과 디시 합쳐질 수 없다. (실제 게임에서는 이동을 한 번 할 때마다 블록이 추가되지만, 이 문제에서 블록이 추가되는 경우는 없다)

이 문제에서 다루는 2048 게임은 보드의 크기가 NxN이다. 보드의 크기와 보드판의 블록 상태가 주어졌을 때, 쵣 5번 이동해서 만들 수 있는 가장 큰 불록의 값을 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 보드의 크기 N (1<=N<=20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2보다 크거나 같고, 1024보다 작거나 같은 2의 제곱꼴이다. 블록은 적어도 하나 주어진다.

출력:

최대 5번 이동시켜서 얻을 수 있는 가장 큰 블록을 출력한다.

풀이방법:

최대 5번만 이동하면 되기 때문에 dfs를 사용해서 모든 경우를 탐색하고, 그 중 가장 최댓값을 찾아내도록 하면 된다.

반복문을 사용해서 상하좌우로 이동하게 만들었다.

문제링크:

www.acmicpc.net/problem/12100