CodeDrive

문제:

Day of Mourning의 기타리스트 강토는 다가오는 공연에서 연주할 N개의 곡을 연주하고 있다. 지금까지 공연과는 다른 공연을 보여주기 위해서 이번 공연에서는 매번 곡이 시작하기 전에 볼륨을 바꾸고 연주하려고 한다.

먼저, 공연이 시작하기 전에 각각의 곡이 시작하기 전에 바꿀 수 있는 볼륨의 리스트를 만들었다. 이 리스트를 V라고 했을 때, V[i]는 i번째 곡을 연주하기 전에 바꿀 수 있는 볼륨을 의미한다. 항상 리스트에 적힌 차이로만 볼륨을 바꿀 수 있다. 즉, 현재 볼륨이 P이고 지금 i번째 곡을 연주하기 전이라면, i번 곡은 P+V[i]나 P-V[i]로 연주 해야 한다. 하지만 0보다 작은 값으로 볼륨을 바꾸거나, M보다 큰 값으로 볼륨을 바꿀 수 없다.

곡의 개수 N과 시작 볼륨 S, 그리고 M이 주어졌을 때, 마지막 곡을 연주할 수 있는 볼륨 중 최댓값을 구하는 프로그램을 작성하시오. 모든 곡은 리스트에 적힌 순서대로 연주해야 한다.

입력:

첫째 줄에 N, S, M이 주어진다. (1<=N<=100, 1<=M<=1000,0<=S<=M) 둘째 줄에는 각 곡이 시작하기 전에 줄 수 있는 볼륨의 차이가 주어진다. 이 값은 1보다 크거나 같고, M보다 작거나 같다.

출력:

첫째 줄에 가능한 마지막 곡의 볼륨 중 최댓값을 출력한다. 만약 마지막 곡을 연주할 수 없다면(중간에 볼륨을 조절을 할 수 없다면) -1을 출력한다.

풀이방법:

 2차원 배열을 사용하는 동적계획법을 사용하면 트리처럼 진행이 된다. 점차 연주가 가능한 볼륨이 많아지긴 하겠지만, 0보다 작은 값이나 초과하는 값들도 들어오기 때문에 생각만큼 많이 증가하지는 않게 된다.

 각 배열은 0으로 초기화 되어 있으며 각 곡마다 연주할 수 있는 볼륨은 1로 바뀌게 된다. 따라서 처음에는 S 자리에만 1로 초기화 되어 있으며 다음 곡의 배열은 이전 곡에서 1인 값에 V[i]를 빼거나 더한 값이 1로 초기화 될 것이다.

 이렇게 마지막 곡까지 위 행위를 반복하고 뒤에서부터 1인 값을 찾아 1이면 값을 넣고 종료시키면 그 값이 최댓값이 될 것이다. 그리고 애초에 -1을 초기값으로 잡아뒀기 때문에 1인 값을 만나지 못하면 연주 할 수 없는 것을 의미하므로 답은 그대로 -1이 될 것이다.

문제링크:

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

문제:

자연수 A를 B번 곱한 수를 알고 싶다. 단 구하려는 수가 매우 커질 수 있으므로 이를 C로 나눈 나머지를 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 A,B,C가 빈 칸을 사이에 두고 순서대로 주어진다. A,B,C는 모두 2,147,483,647 이하의 자연수이다.

출력:

첫째 줄에 A를 B번 곱한 수를 C로 나눈 나머지를 출력한다.

풀이방법:

 주어질 A,B,C의 값이 매우 크므로 pow 연산을 활용하는 것은 시간초과가 발생하게 될 것이다. 따라서 효율적인 연산이 필요하다. 그러면서 사용하게 되는 것이 모듈러 연산의 분배법칙이다.

 모듈러  X=x1*x2라고 가정하자. 그러면 X mod y = (x1 mod y)*(x2 mod y) mod y 가 성립한다. 이 것과 10^n*10^m=10^(n+m)임을 사용하면 시간복잡도를 O((logN)^2)까지 줄일 수 있다.

 우선 지수를 2의 지수 단위로 분할한다. 이 문제의 예시와 같은 경우 11은 8+2+1로 482는 256+128+64+32+2와 같이 분할할 수 있다. 즉 10^11 mod 12 = (10^8 mod 12)(10^2 mod 12)(10^1 mod 12) mod 12 이고, 10^482 mod 12 = (10^256 mod 12)(10^128 mod 12)(10^64 mod 12)(10^32 mod 12)(10^2 mod 12) mod 12가 된다.

  2의 지수를 사용하는 것에는 이유가 있다. 10^1부터 DP 방식을 사용하면 나머지의 값들도 쉽게 구할 수 있기 때문이다. 10^2 mod 12 = (10^1 mod 12)(10^1 mod 12) mod 12 이고 10^4 mod 12 = (10^2 mod 12)(10^2 mod 12) mod 12 ...와 같이 구하면 된다.

 위와 같이 dp table을 다 채우고 난 뒤에 해당하는 값들만 곱한뒤에 다시 c로 나누면 나머지를 출력하면 된다.

문제링크:

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

문제:

 NxN 게임판에 수가 적혀져 있다. 이 게임의 목표는 가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 점프를 해서 가는 것이다.

 각 칸에 적혀있는 수는 현재 칸에서 갈 수 있는 거리를 의미한다. 반드시 오른쪽이나 아래쪽으로만 이동해야 한다. 0은 더 이상 진행을 막는 종착점이며, 항상 현재 칸에 적혀있는 수만큼 오른쪽이나 아래로 가야 한다. 한 번 점프를 할 때, 방향을 바꾸면 안 된다. 즉, 한 칸에서 오른쪽으로 점프를 하거나, 아래로 점프를 하는 두 경우만 존재한다.

 가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 이동할 수 있는 경로의 개수를 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 게임 판의 크기 N(4<=N<=100)이 주어진다. 그 다음 N개 줄에는 각 칸에 적혀져 있는 수가 N개씩 주어진다. 칸에 적혀있는 수는 0보다 크거나 같고, 9보다 작거나 같은 정수이며, 가장 오른쪽 아래 칸에는 항상 0이 주어진다.

출력:

가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 문제의 규칙에 맞게 갈 수 있는 경로의 개수를 출력한다. 경로의 개수를 2^63-1보다 작거나 같다.

풀이방법:

 dp를 사용해서 값을 누적시키면서 진행하면 답을 구할 수 있다. 갈 수 있는 경로의 수만 알면 되므로 dp[i][j]로 갈 수 있는 경우의 수를 누적시키면서 n,n으로 진행해나가면 된다. 따라서 시간복잡도는 O(N^2)이 될 것이다. dp[i][j]로 갈 수 있는 방법은 크게 두 가지다. 해당 위치를 기준으로 왼쪽에서 오거나 위쪽에서 오는 경우이다. 해당 칸에서 이동이 가능한지 알아보고 가능하다면 값을 더해주는 방식으로 진행하면 된다.

문제링크:

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

문제:

상담원으로 일하고 있는 백준이는 퇴사를 하려고 한다.

오늘부터 N+1일째 되는 날 퇴사를 하기 위해서, 남은 N일 동안 최대한 많은 상담을 하려고 한다.

백준이는 비서에게 최대한 많은 상담을 잡으라고 부탁을 했고, 비서는 하루에 하나씩 서로 다른 사람의 상담을 잡아놓았다.

각각의 상담은 상담을 완료하는데 걸리는 시간 Ti와 상담을 했을 때 받을 수 있는 금액 Pi로 이루어져 있다.

N=7인 경우에 다음과 같은 상담 일정표를 보자.

 1일에 잡혀있는 상담은 총 3일이 걸리며, 상담했을 때 받을 수 있는 금액은 10이다. 5일에 잡혀있는 상담은 총 2일이 걸리며, 받을 수 있는 금액은 15이다.

상담을 하는데 필요한 기간은 1일보다 클 수 있기 때문에, 모든 상담을 할 수는 없다. 예를 들어서 1일에 상담을 하게 되면, 2일, 3일에 있는 상담은 할 수 없게 된다. 2일에 있는 상담을 하게 되면, 3,4,5,6 일에 잡혀있는 상담은 할 수 없다.

또한, N+1일째에는 회사에 없기 때문에, 6,7이렝 있는 상담을 할 수 없다.

퇴사 전에 할 수 있는 상담의 최대 이익은 1일, 4일, 5일에 있는 상담을 하는 것이며, 이 때의 이익은 10+20+15=45이다.

상담을 적절히 했을 때, 백준이가 얻을 수 있는 최대 수익을 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 N(1<=N<=15)이 주어진다.

둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1<=Ti<=5,1<=Pi<=1,000)

출력:

첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다.

풀이방법:

기간을 넘어가서 상담을 할 수는 없는 것이므로 뒤에서 부터 값을 업데이트 하며 오도록 하였다. i일의 최대 가능한 금액은 이전의 값을 그대로 가져오가나 몇일 지난 값을 더한 값이 되게 된다. 따라서 이 점화식에 따라서 계속해서 값을 구하다 보면 d[0]에 최대값이 담기게 된다.

문제링크:

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

문제:

상근이와 선영이가 다른 사람들의 남매간의 대화를 듣는 것을 방지하기 위해서 대화를 서로 암호화 하기로 했다.. 그래서 다음과 같은 대화를 했다.

• 상근: 그냥 간단히 암호화 하자. A를 1이라고 하고, B는 2로, 그리고 Z는 26으로 하는거야.
• 선영: 그럼 안돼. 만약, "BEAN"을 암호화하면 25114가 나오는데, 이걸 다시 글자로 바꾸는 방법은 여러 가지가 있어
• 상근: 그렇네. 25114를 다시 영어로 바꾸면, "BEAAD", "YAAD", "YAN", "YKD", "BEKD", " BEAN" 총 6가지가 나오는데, BEAN이 맞는 단어라는건 쉽게 알수 있잖아?
• 선영: 예가 적절하지 않았네 ㅠㅠ 만약 내가 500자리 글자를 암호화 했다고 해봐. 그 때는 나올 수 있는 해석이 정말 많은데, 그걸 언제 다해봐?
• 상근: 얼마나 많은데?
• 선영: 구해보자!

어떤 암호가 주어졌을 때, 그 암호의 해석이 몇 가지가 나올 수 있는지 구하는 프로그램을 작정하시오.

입력:

첫째 줄에 5000자리 이하의 암호가 주어진다. 암호는 숫자로 이루어져 있다.

출력:

나올 수 있는 해석의 가짓수를 구하시오. 정잡이 매우 클 수 있으므로, 1000000으로 나눈 나머지를 출력한다.

풀이방법:

하나의 숫자에 대해 두가지 경우가 있을 수 있다. 한자리 수 일 경우 (1~9, A~J) ,두자리 수일 경우 (10~26,K~Z)이다. 따라서 d[i]는 d[i-1] 와 d[i-2] 값을 합친 값임을 알 수 있다. (물론 조건에 맞는것만) 따라서 조건에 맞을 때마다 값을 더해주면 되는데 이 때, 몇 개의 예외처리를 해주면 된다.

 우선 index가 맨처음일 때, 두 자리일수가 없다. 따라서 이 경우에는 continue로 넘어간다.

 또한 i-1이 0일 때, 01,02,.....와 같은 경우는 두 자리수가 아닌 한자리수이다. 따라서 고려 대상이 아니다.

더하면서 매번 mod 값으로 나눠주면 쉽게 구할 수 있다.

문제링크:

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

문제:

3 x N 크기의 벽을 2x1,1x2 크기의 타일로 채우는 경우의 수를 구해보자.

입력:

첫째 줄에 N(1<=N<=30)이 주어진다.

출력:

첫째 줄에 경우의 수를 출력한다.

풀이방법:

홀수인 경우는 만들 수 없으니 제외를 하고 각 n은 이전 값의 3배에다가 더 이전의 값들의 2배씩을 더한 값들이다.

문제링크:

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

문제:

어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=3^2+1^2+1^2(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=2^2+2^2+1^2+1^2+1^2(5개 항)도 가능하다. 이 경우, 수학자 숌크라테스는 "11은 3개 항의 제곱수 합으로 표현할 수 있다."라고 말한다. 또한 11은 그보다 적은 항의 제곱수 합으로 표현할 수 없으므로, 11을 그 합으로써 표현할 수 있는 제곱수 항의 최소 개수는 3이다.

 주어진 자연수 N을 이렇게 제곱수들의 합으로 표현할 때에 그 항의 최소개수를 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 자연수 N이 주어진다. (1<=N<=100,000)

출력:

주어진 자연수를 제곱수의 합으로 나타낼 때에 그 제곱수 항의 최소 개수를 출력한다.

풀이 방법:

동적 계획법으로 쉽게 풀 수 있는 문제이다. 11은 다음과 같이 표현 될 수 있다. 11-3^2=1^2+1^2 와 11-2^2=2^2+1^2+1^2+1^2 와 같이 생각할 수 있다. 따라서 모든 수들이 이와 같이 증가한다고 가정을 하고 최소항을 사용한 경우에만 업데이트도록 해서 최소개수를 나타내도록 하였다.

문제 링크:

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

문제:

 상근이의 여동생 상냥이는 문방구에서 스티커 2n개를 구매했다. 스티커는 그림(a)와 같이 2행 n열로 배치되어 있다. 상냥이는 스티커를 이용해 책상을 꾸미려고 한다.

 상냥이가 구매한 스티커의 품질은 매우 좋지 않다. 스티커 한 장을 뗴면, 그 스티커와 변을 공유하는 스티커는 모두 찢어져서 사용할 수 없게 된다. 즉, 뗀 스티커의 왼쪽, 오른쪽, 위, 아래에 있는 스티커는 사용할 수 없게 된다.

모든 스티커를 붙일 수 없게 된 상냥이는 각 스티커에 점수를 매기고, 점수의 합이 최대가 되게 스티커를 떼어내려고 한다. 먼저, 그림 (b)와 같이 각 스티커에 점수를 매겼다. 상냥이가 뗄 수 있는 스티커의 점수의 최댓값을 구하는 프로그램을 작성하시오. 즉, 2n개의 스티커 중에서 점수의 합이 최대가 되면서 서로 변을 공유 하지 않는 스티커 집합을 구해야 한다.

위의 그림의 경우에 점수가 50,50,100,60인 스티커를 고르면, 점수는 260이 되고 이 것이 최대 점수이다. 가장 높은 점수를 가지는 두 스티커(100과 70)은 변을 공유하기 때문에, 동시에 뗄 수 없다.

입력:

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1<=n<=100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 점수이다. 연속하는 두 정수 사이에는 빈 칸이 하나 있다. 점수는 0보다 크거나 같고, 100보다 작거나 같은 정수이다.

출력:

각 테스트 케이스 마다, 2n개의 스티커 중에서 두 변을 공유하지 않는 스티커 점수의 최댓값을 출력한다.

풀이 방법:

 열 단위로 끊어가면서 동적계획법을 적용하면 된다. 한 열에서 뗄 수 있는 경우의 수는 총 3가지이다.

  1 . 위, 아래 둘다 뜯지 않을 경우

  2.  위만 뜯을 경우

  3.  아래만 뜯을 경우

따라서 이 규칙대로 뜯어나가면서 최댓값을 찾아나가면 된다.

 i번째 열에서 1번의 경우로 뜯기 위해선 i-1열에는 1,2,3 모든 경우의 수가 올 수 있다. 따라서 i-1열의 값 중 최댓값을 그대로 가져오면 된다.

 i번째 열에서 2번의 경우로 뜯기 위해선 i-1열에는 1,3만 올 수 있다. 따라서 이 두 값중 최대값과 i번째 위 값을 더해주면 된다.

 i번째 열에서 3번의 경우로 뜯기 위해선 i-1열에는 1,2만 올 수 있다. 따라서 이 두 값중 최대값과 i번째 아래 값을 더해주면 된다.

이렇게 n번째 열(인덱스 상으론 n-1)까지 위와 같은 규칙으로 계속 업데이트 해준 다음에 최댓값을 찾으면 전체의 최댓값을 알 수 있게 된다.

문제 링크:

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

문제:

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50}인 경우에 가장 긴 증가하는 부분 수열은 A={10, 20, 10, 30, 20, 50}이고, 길이는 4이다.

입력:

첫째 줄에 수열 A의 크기(1<=N<=1,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1<=Ai<=1,000)

출력:

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

풀이 방법:

배열을 하나씩 커지게 만들어 가면서 증가하는 부분 수열을 찾도록 한다. 가장 큰 값을 빠르게 찾기 위해서 뒤에서 부터 값을 탐색하도록 하게 한다.

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

문제:

어떤 동물원에 가로로 두 칸 세로로 N칸인 아래와 같은 우리가 있다.

이 동물원에는 사자들이 살고 있는데 사자들을 우리에 가둘 때, 가로로도 세로로도 불어 있게 배치할 수는 없다.

이 동물원 조련사는 사자들의 배치 문제 때문에 골머리를 앓고 있다.

동물원 조련사의 머리가 아프지 않도록 우리가 2*N 배열에 사자를 배치하는 경우의 수가 몇 가지인지를 알아내는 프로그램을 작성해 주도록 하자. 사자를 한 마리도 배치하지 않는 경우도 하나의 경우의 수로 친다고 가정한다.

입력:

첫째 줄에 우리의 크기 N(1<=N<=100,000)이 주어진다.

출력:

첫째 줄에 사자를 배치하는 경우의 수를 9901로 나눈 나머지를 출력하여라.

풀이 방법:

 dp문제인데 N마다 생성되는 규칙을 찾아내거나 아니면 점화식을 찾으면 된다. 따라서 찾은 점화식은 다음과 같다. 

an = a(n-1) + 2*a(n-2)

따라서 이 규칙에 따라서 값을 구해주면 된다.

문제 링크:

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