CodeDrive

문제:

영선이는 숫자가 쓰여 있는 직사각형 종이를 가지고 있다. 종이는 1×1 크기의 정사각형 칸으로 나누어져 있고, 숫자는 각 칸에 하나씩 쓰여 있다. 행은 위에서부터 아래까지 번호가 매겨져 있고, 열은 왼쪽부터 오른쪽까지 번호가 매겨져 있다.

영선이는 직사각형을 겹치지 않는 조각으로 자르려고 한다. 각 조각은 크기가 세로나 가로 크기가 1인 직사각형 모양이다. 길이가 N인 조각은 N자리 수로 나타낼 수 있다. 가로 조각은 왼쪽부터 오른쪽까지 수를 이어 붙인 것이고, 세로 조각은 위에서부터 아래까지 수를 이어붙인 것이다.

아래 그림은 4×4 크기의 종이를 자른 한 가지 방법이다.

각 조각의 합은 493 + 7160 + 23 + 58 + 9 + 45 + 91 = 7879 이다.

종이를 적절히 잘라서 조각의 합을 최대로 하는 프로그램을 작성하시오.

입력:

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

둘째 줄부터 종이 조각이 주어진다. 각 칸에 쓰여 있는 숫자는 0부터 9까지 중 하나이다.

출력:

영선이가 얻을 수 있는 점수의 최댓값을 출력한다.

풀이방법:

 비트마스킹을 사용하여 해당 문제를 풀었다. N*M의 크기의 직사각형을 0,1의 비트마스킹으로 표현한다. 이 때 0은 가로로 연결되는 경우를 의미하고, 1은 세로로 연결되는 경우를 의미하게 된다.

 주어진 케이스에 대해 가로와 각각 따로 계산을 수행하도록 한다. 가로는 idx가 0인 경우에 대해서만 이어붙이며 값을 누적시키도록 한다. 반대로 세로는 idx가 1인 경우에 대해서만 이어붙이고 값을 누적시킨다. 모든 케이스에 대해서 이 작업을 반복 수행하며 가장 큰 경우를 출력하도록 한다.

문제링크:

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

문제:

각각 부피가 A, B, C(1≤A, B, C≤200) 리터인 세 개의 물통이 있다. 처음에는 앞의 두 물통은 비어 있고, 세 번째 물통은 가득(C 리터) 차 있다. 이제 어떤 물통에 들어있는 물을 다른 물통으로 쏟아 부을 수 있는데, 이때에는 한 물통이 비거나, 다른 한 물통이 가득 찰 때까지 물을 부을 수 있다. 이 과정에서 손실되는 물은 없다고 가정한다.

이와 같은 과정을 거치다보면 세 번째 물통(용량이 C인)에 담겨있는 물의 양이 변할 수도 있다. 첫 번째 물통(용량이 A인)이 비어 있을 때, 세 번째 물통(용량이 C인)에 담겨있을 수 있는 물의 양을 모두 구해내는 프로그램을 작성하시오.

입력:

첫째 줄에 세 정수 A, B, C가 주어진다.

출력:

첫째 줄에 공백으로 구분하여 답을 출력한다. 각 용량은 오름차순으로 정렬한다.

풀이방법:

A, B를 담을 수 있는 물통들을 기준으로 하여 visited 배열을 만들고, BFS를 수행하도록 한다. visited의 가능한 갯수는 A와 B에 담을 수 있는 경우의 수와 같다. 처음은 비어있기 때문에, (0,0)으로부터 시작하도록 한다. 매 C는 가지고 있는 A, B 물의 양을 통해 구하도록 한다. 가지고 있는 A, B, C 물의 양을 통해 이동할 수 있는 모든 경우에 대해 조사하도록 한다. (A-> B, A-> C, B->C, B-> A, C-> A, C-> B)와 같은 총 6가지 case가 존재한다. 가능한 모든 경우에 대해 BFS를 수행하며 A의 물의 양이 0인 경우에 C의 값을 저장하도록 한다.

문제링크:

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

문제:

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.

• 1+1+1+1
• 1+1+2
• 1+2+1
• 2+1+1
• 2+2
• 1+3
• 3+1

정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 1,000,000보다 작거나 같다.

출력:

각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다.

풀이방법:

 이전 1, 2, 3 더하기 문제에서는 재귀형태로 문제를 풀었지만 이번에는 숫자의 범위가 크기 때문에 시간초과가 발생할 것이다. 따라서 이번에는 dp 배열을 사용하여 문제를 풀도록 한다. 

 점화식은 간단한 편이다. N을 만들기 위해서 N-3의 경우에서 3을 N-2의 경우에서 2를 N-1일 대는 1을 각각 더해주면 되기 때문이다. 즉, dp[N] = dp[N-1] + dp[N-2] + dp[N-3]과 같다.

1000000까지 dp를 만든 뒤에 N 값을 출력하도록 한다.

문제링크:

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

문제:

BOJ 알고리즘 캠프에는 총 N명이 참가하고 있다. 사람들은 0번부터 N-1번으로 번호가 매겨져 있고, 일부 사람들은 친구이다.

오늘은 다음과 같은 친구 관계를 가진 사람 A, B, C, D, E가 존재하는지 구해보려고 한다.

• A는 B와 친구다.
• B는 C와 친구다.
• C는 D와 친구다.
• D는 E와 친구다.

위와 같은 친구 관계가 존재하는지 안하는지 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 사람의 수 N (5 ≤ N ≤ 2000)과 친구 관계의 수 M (1 ≤ M ≤ 2000)이 주어진다.

둘째 줄부터 M개의 줄에는 정수 a와 b가 주어지며, a와 b가 친구라는 뜻이다. (0 ≤ a, b ≤ N-1, a ≠ b) 같은 친구 관계가 두 번 이상 주어지는 경우는 없다.

출력:

문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다.

풀이방법:

 처음에는 문제를 조금 이해하는 것이 어려웠다. 주어진 모든 사람의 관계가 조건과 같이 구성되어야 하는줄 알았는데, 일부 사람들만 관계를 유지하면 된다. 따라서 N명의 사람들의 관계를 트리 형태로 구성했을 때, 하나의 노드로부터 깊이가 4인 경우가 있는지 확인하면 된다.

 따라서 처음에는 주어진 관계들을 양방향 그래프로 정리를 한다. 그 다음에는 각 노드로부터 dfs를 수행했을 때, 깊이가 4인 경우가 있는지 확인한다. 깊이가 4인 경우가 한 개라도 있으면 되기 때문에 찾았다면 탐색을 중지하고 1을 출력하며, 모든 노드로부터 탐색했는데 없다면 0을 출력하도록 한다.

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

문제:

민식이는 수학학원에서 단어 수학 문제를 푸는 숙제를 받았다.

단어 수학 문제는 N개의 단어로 이루어져 있으며, 각 단어는 알파벳 대문자로만 이루어져 있다. 이때, 각 알파벳 대문자를 0부터 9까지의 숫자 중 하나로 바꿔서 N개의 수를 합하는 문제이다. 같은 알파벳은 같은 숫자로 바꿔야 하며, 두 개 이상의 알파벳이 같은 숫자로 바뀌어지면 안 된다.

예를 들어, GCF + ACDEB를 계산한다고 할 때, A = 9, B = 4, C = 8, D = 6, E = 5, F = 3, G = 7로 결정한다면, 두 수의 합은 99437이 되어서 최대가 될 것이다.

N개의 단어가 주어졌을 때, 그 수의 합을 최대로 만드는 프로그램을 작성하시오.

입력:

첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 10개이고, 수의 최대 길이는 8이다. 서로 다른 문자는 서로 다른 숫자를 나타낸다.

출력:

첫째 줄에 주어진 단어의 합의 최댓값을 출력한다.

풀이방법:

 모든 케이스에 대해 수행하기에는 경우의 수가 너무 많기 때문에 그리디하게 이 문제를 해결하도록 한다. 각 알파벳에 대해 가중치를 구한 뒤에 가중치가 높은 순서대로 9부터 숫자를 할당하면 된다.

 가중치는 알파벳이 있는 위치, 갯수에 따라 다르게 설정한다. ABC와 같이 있을 때, 이를 숫자로 보면 A00, B0, C와 같다. 즉 자릿수가 클수록 더 높은 가중치를 가지게 된다. 따라서 word를 순회하면서 가중치를 순회하도록 한다. 이를 dict 형태로 저장하는데, 불필요한 키들을 줄이기 위해 defaultdict을 사용하여 깔끔하게 정리하도록 한다.

 최종적으로는 가중치에 따라 값을 부여하고 합을 누적시키도록 한다.

문제링크:

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

문제:

N개의 수로 이루어진 수열 A1, A2, ..., AN이 주어진다. 또, 수와 수 사이에 끼워넣을 수 있는 연산자가 주어진다. 연산자는 덧셈(+), 뺄셈(-), 곱셈(×), 나눗셈(÷)으로만 이루어져 있다. 연산자의 개수는 N-1보다 많을 수도 있다. 모든 수의 사이에는 연산자를 한 개 끼워넣어야 하며, 주어진 연산자를 모두 사용하지 않고 모든 수의 사이에 연산자를 끼워넣을 수도 있다.

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

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

• 1+2+3-4×5÷6
• 1÷2+3+4-5×6
• 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
• 1+2+3+4-5-6 = -1
• 1+2+3-4-5×6 = -18

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

입력:

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

출력:

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

풀이방법:

 처음에는 이 문제를 permutation을 사용해서 풀려고 했으나 시간초과나 메모리초과가 발생하게 되었다. 따라서 조금 더 효율적인 방법을 찾고자 고안한 방법은 백트래킹 방법이다.

 permutation은 매 candidate마다 값을 계산해야 한다. 하지만 1,1,3이라는 숫자가 있을 때, 1+1을 한번만 구한 뒤에 3에다가 추가적인 연산을 하는 것이 더 효율적이다. 따라서 dfs를 사용해서 백트래킹 방법을 사용하여 모든 케이스에 대해 연산을 수행하도록 한다. 

문제링크:

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

문제:

크기가 3×3인 배열 A가 있다. 배열의 인덱스는 1부터 시작한다. 1초가 지날때마다 배열에 연산이 적용된다.

• R 연산: 배열 A의 모든 행에 대해서 정렬을 수행한다. 행의 개수 ≥ 열의 개수인 경우에 적용된다.
• C 연산: 배열 A의 모든 열에 대해서 정렬을 수행한다. 행의 개수 < 열의 개수인 경우에 적용된다.

한 행 또는 열에 있는 수를 정렬하려면, 각각의 수가 몇 번 나왔는지 알아야 한다. 그 다음, 수의 등장 횟수가 커지는 순으로, 그러한 것이 여러가지면 수가 커지는 순으로 정렬한다. 그 다음에는 배열 A에 정렬된 결과를 다시 넣어야 한다. 정렬된 결과를 배열에 넣을 때는, 수와 등장 횟수를 모두 넣으며, 순서는 수가 먼저이다.

예를 들어, [3, 1, 1]에는 3이 1번, 1가 2번 등장한다. 따라서, 정렬된 결과는 [3, 1, 1, 2]가 된다. 다시 이 배열에는 3이 1번, 1이 2번, 2가 1번 등장한다. 다시 정렬하면 [2, 1, 3, 1, 1, 2]가 된다.

정렬된 결과를 배열에 다시 넣으면 행 또는 열의 크기가 달라질 수 있다. R 연산이 적용된 경우에는 가장 큰 행을 기준으로 모든 행의 크기가 변하고, C 연산이 적용된 경우에는 가장 큰 열을 기준으로 모든 열의 크기가 변한다. 행 또는 열의 크기가 커진 곳에는 0이 채워진다. 수를 정렬할 때 0은 무시해야 한다. 예를 들어, [3, 2, 0, 0]을 정렬한 결과는 [3, 2]를 정렬한 결과와 같다.

행 또는 열의 크기가 100을 넘어가는 경우에는 처음 100개를 제외한 나머지는 버린다.

배열 A에 들어있는 수와 r, c, k가 주어졌을 때, A[r][c]에 들어있는 값이 k가 되기 위한 최소 시간을 구해보자.

입력:

첫째 줄에 r, c, k가 주어진다. (1 ≤ r, c, k ≤ 100)

둘째 줄부터 3개의 줄에 배열 A에 들어있는 수가 주어진다. 배열 A에 들어있는 수는 100보다 작거나 같은 자연수이다.

출력:

A[r][c]에 들어있는 값이 k가 되기 위한 연산의 최소 시간을 출력한다. 100초가 지나도 A[r][c] = k가 되지 않으면 -1을 출력한다.

풀이방법:

 연산에 따라 행과 열에 각각 행동을 취해야 하는 문제다. 일반적으로 열에다가 특정 연산을 취하는 것은 어렵기 때문에 열에 있는 내용들을 50번줄과 같이 행으로 전환해서 수행하도록 한다.

 각 행을 dict을 사용해서 갯수를 count하고 (횟수, 숫자)를 기준으로 정렬하도록 한다. 각 행을 임시 배열에 저장한 뒤에 가장 긴 행을 기준으로 나머지 부분에 0을 채워넣도록 한다. 만약 열에 대해서 수행했다면 50번줄의 코드를 다시 실행하여 열로 바꿔주도록 한다. 이를 k를 찾거나 100초가 넘을때까지 계속 반복해서 수행한다.

문제링크:

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

문제:

위와 같은 십자모양의 한 장의 카드에서, 네 모서리에 1 이상 9 이하의 숫자가 하나씩 씌여 있다. 이 네 개의 숫자 중에는 같은 숫자도 있을 수 있다.

모든 가능한 십자 카드가 주어질 때, 각각의 카드는 다음과 같은 '시계수'라는 번호를 가진다. 시계수는 카드의 숫자들을 시계 방향으로 읽어서 만들어지는 네 자리 수들 중에서 가장 작은 수이다. 위 그림의 카드는 시계방향으로 3227, 2273, 2732, 7322로 읽을 수 있으므로, 이 카드의 시계수는 가장 작은 수인 2273이다.

입력으로 주어진 카드의 시계수를 계산하여, 그 시계수가 모든 시계수들 중에서 몇 번째로 작은 시계수인지를 알아내는 프로그램을 작성하시오.

예를 들어서, 다음과 같은 십자 카드의 시계수는 1122이며, 이 시계수보다 작은 시계수들은 1111, 1112, 1113, 1114, 1115, 1116, 1117, 1118, 1119 뿐이므로 1122는 10번째로 작은 시계수다. (여기서 십자카드는 0 이 나타날 수 없으므로 1120은 시계수가 될 수 없다. 또한 1121 이 적혀있는 카드의 시계수는 1112이므로, 1121은 시계수가 될 수 없다.

입력:

입력은 한 줄로 이루어지며, 이 한 줄은 카드의 네 모서리에 씌여있는 1 이상 9 이하의 숫자 4개가 시계 방향으로 입력된다. 각 숫자 사이에는 빈칸이 하나 있다.

출력:

입력된 카드의 시계수가 모든 시계수들 중에서 몇 번째로 작은 시계수인지를 출력한다.

풀이방법:

 1111부터 시작해서 주어진 수의 시계수까지 하나씩 다 구하면서 몇 번째인지 출력하도록 한다.

우선 입력된 카드의 시계수를 구한 뒤에 1111부터 해당 시계수까지 while로 반복한다. 이 때, 1120, 1121와 같이 시계수가 아닌 경우도 있기 때문에 해당 경우는 조건문을 사용하여 제외하도록 한다. 또한 회전연산을 쉽게 하기 위해 collections에 있는 deque의 rotate를 사용했다.

문제링크:

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

문제:

세로 두 줄, 가로로 N개의 칸으로 이루어진 표가 있다. 첫째 줄의 각 칸에는 정수 1, 2, …, N이 차례대로 들어 있고 둘째 줄의 각 칸에는 1이상 N이하인 정수가 들어 있다. 첫째 줄에서 숫자를 적절히 뽑으면, 그 뽑힌 정수들이 이루는 집합과, 뽑힌 정수들의 바로 밑의 둘째 줄에 들어있는 정수들이 이루는 집합이 일치한다. 이러한 조건을 만족시키도록 정수들을 뽑되, 최대로 많이 뽑는 방법을 찾는 프로그램을 작성하시오. 예를 들어, N=7인 경우 아래와 같이 표가 주어졌다고 하자.

이 경우에는 첫째 줄에서 1, 3, 5를 뽑는 것이 답이다. 첫째 줄의 1, 3, 5밑에는 각각 3, 1, 5가 있으며 두 집합은 일치한다. 이때 집합의 크기는 3이다. 만약 첫째 줄에서 1과 3을 뽑으면, 이들 바로 밑에는 정수 3과 1이 있으므로 두 집합이 일치한다. 그러나, 이 경우에 뽑힌 정수의 개수는 최대가 아니므로 답이 될 수 없다.

입력:

첫째 줄에는 N(1≤N≤100)을 나타내는 정수 하나가 주어진다. 그 다음 줄부터는 표의 둘째 줄에 들어가는 정수들이 순서대로 한 줄에 하나씩 입력된다.

출력:

첫째 줄에 뽑힌 정수들의 개수를 출력하고, 그 다음 줄부터는 뽑힌 정수들을 작은 수부터 큰 수의 순서로 한 줄에 하나씩 출력한다.

풀이방법:

 뽑힌 정수들이 이루는 집학과 뽑힌 정수들의 바로 밑의 둘째 줄에 들어있는 정수들이 이루는 집합이 일치한다는 것은 그 해당 정수들로 사이클이 이뤄진다는 것과 동일하다. 즉, 이 문제는 숫자 배열들 중에서 가장 큰 사이클을 찾으면 된다.

 따라서 사이클을 찾기 위해 DFS를 사용하여 문제를 풀도록 한다.

문제링크:

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

문제:

봄버맨은 크기가 R×C인 직사각형 격자판 위에서 살고 있다. 격자의 각 칸은 비어있거나 폭탄이 들어있다.

폭탄이 있는 칸은 3초가 지난 후에 폭발하고, 폭탄이 폭발한 이후에는 폭탄이 있던 칸이 파괴되어 빈 칸이 되며, 인접한 네 칸도 함께 파괴된다. 즉, 폭탄이 있던 칸이 (i, j)인 경우에 (i+1, j), (i-1, j), (i, j+1), (i, j-1)도 함께 파괴된다. 만약, 폭탄이 폭발했을 때, 인접한 칸에 폭탄이 있는 경우에는 인접한 폭탄은 폭발 없이 파괴된다. 따라서, 연쇄 반응은 없다.

봄버맨은 폭탄에 면역력을 가지고 있어서, 격자판의 모든 칸을 자유롭게 이동할 수 있다. 봄버맨은 다음과 같이 행동한다.

• 가장 처음에 봄버맨은 일부 칸에 폭탄을 설치해 놓는다. 모든 폭탄이 설치된 시간은 같다.
• 다음 1초 동안 봄버맨은 아무것도 하지 않는다.
• 다음 1초 동안 폭탄이 설치되어 있지 않은 모든 칸에 폭탄을 설치한다. 즉, 모든 칸은 폭탄을 가지고 있게 된다. 폭탄은 모두 동시에 설치했다고 가정한다.
• 1초가 지난 후에 3초 전에 설치된 폭탄이 모두 폭발한다.
• 3과 4를 반복한다.

폭탄을 설치해놓은 초기 상태가 주어졌을 때, N초가 흐른 후의 격자판 상태를 구하려고 한다.

예를 들어, 초기 상태가 아래와 같은 경우를 보자.

1초가 지난 후에는 아무 일도 벌어지지 않기 때문에, 위와 같다고 볼 수 있다. 1초가 더 흐른 후에 격자판의 상태는 아래와 같아진다.

1초가 지난 후엔 가운데에 있는 폭탄이 폭발해 가운데 칸과 인접한 네 칸이 빈 칸이 된다.

입력:

첫째 줄에 R, C, N (1 ≤ R, C, N ≤ 200)이 주어진다. 둘째 줄부터 R개의 줄에 격자판의 초기 상태가 주어진다. 빈 칸은 '.'로, 폭탄은 'O'로 주어진다.

출력:

총 R개의 줄에 N초가 지난 후의 격자판 상태를 출력한다.

풀이방법:

 문제의 조건대로 폭탄을 설치하고 터트리는 과정을 반복하면 된다. 문제에서는 설치하는 과정, 폭발하는 과정이 1초씩 각각 수행되는 것으로 나타나지만 같은 while에서 수행하도록 한다.

 현재 지도에서 폭탄이 있는 위치를 찾아 좌표만을 저장한 후 빈 공간에 폭탄을 모두 채워 넣는다.( 따라서 매 짝수초마다 폭탄으로 가득찬 지도를 얻는다.) 그리고 폭탄을 설치하기 전에 찾았던 폭탄의 위치를 근거로만 폭탄을 제거하도록 한다.

문제링크:

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