CodeDrive

문제:

재귀 호출만 생각하면 신이 난다! 아닌가요?

다음과 같은 재귀함수 w(a, b, c)가 있다.

위의 함수를 구현하는 것은 매우 쉽다. 하지만, 그대로 구현하면 값을 구하는데 매우 오랜 시간이 걸린다. (예를 들면, a=15, b=15, c=15)

a, b, c가 주어졌을 때, w(a, b, c)를 출력하는 프로그램을 작성하시오.

입력:

입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다.

출력:

입력으로 주어진 각각의 a, b, c에 대해서, w(a, b, c)를 출력한다.

풀이방법:

그냥 이 함수를 재귀로 구성하면 시간초과가 발생하게 된다. 따라서 각 결과를 dp 테이블에 저장함으로써 시간을 단축시키도록 한다.

문제링크:

www.acmicpc.net/problem/9184

문제:

카드게임이 있다. 게임에 사용하는 각 카드에는 양의 정수 하나가 적혀있고 같은 숫자가 적힌 카드는 여러 장 있을 수 있다. 게임방법은 우선 짝수개의 카드를 무작위로 섞은 뒤 같은 개수의 두 더미로 나누어 하나는 왼쪽에 다른 하나는 오른쪽에 둔다.

각 더미의 제일 위에 있는 카드끼리 서로 비교하며 게임을 한다. 게임 규칙은 다음과 같다. 지금부터 왼쪽 더미의 제일 위 카드를 왼쪽 카드로, 오른쪽 더미의 제일 위 카드를 오른쪽 카드로 부르겠다.

1. 언제든지 왼쪽 카드만 통에 버릴 수도 있고 왼쪽 카드와 오른쪽 카드를 둘 다 통에 버릴 수도 있다. 이때 얻는 점수는 없다.

2. 오른쪽 카드에 적힌 수가 왼쪽 카드에 적힌 수보다 작은 경우에는 오른쪽 카드만 통에 버릴 수도 있다. 오른쪽 카드만 버리는 경우에는 오른쪽 카드에 적힌 수만큼 점수를 얻는다.

3. (1)과 (2)의 규칙에 따라 게임을 진행하다가 어느 쪽 더미든 남은 카드가 없다면 게임이 끝나며 그때까지 얻은 점수의 합이 최종 점수가 된다.

왼쪽 더미의 카드에 적힌 정수가 담긴 배열 left와 오른쪽 더미의 카드에 적힌 정수가 담긴 배열 right가 매개변수로 주어질 때, 얻을 수 있는 최종 점수의 최대값을 return 하도록 solution 함수를 작성하시오.

풀이방법:

동적 계획법을 사용해서 푸는 문제이다. 오른쪽을 버릴 때에만 점수를 얻을 수 있으므로, 오른쪽을 많이 버릴 수 있으면 좋다. 그래서 우선 오른쪽을 먼저 버릴 수 있는지 확인을 하고, 왼쪽과 둘 다 버리는 경우를 생각해서 계산한다.

문제링크:

https://programmers.co.kr/learn/courses/30/lessons/42896

문제:

서울에서 경산까지 여행을 하면서 모금 활동을 하려 합니다. 여행은 서울에서 출발해 다른 도시를 정해진 순서대로 딱 한 번 방문한 후 경산으로 도착할 예정입니다. 도시를 이동할 때에는 도보 혹은 자전거를 이용합니다. 이때 도보 이동에 걸리는 시간, 도보 이동 시 얻을 모금액, 자전거 이동에 걸리는 시간, 자전거 이동 시 얻을 모금액이 정해져 있습니다. K시간 이내로 여행할 때 모을 수 있는 최대 모금액을 알아보려 합니다

예를 들어 여행 루트가 다음과 같고 K=1,650 일 때,

1, 2번 구간은 도보로, 3번 구간은 자전거로 이동해 모금액을 660으로 하는 것이 가장 좋은 방법입니다. 이때, 1,600시간이 소요됩니다.

solution 함수의 매개변수로 각 도시를 이동할 때 이동 수단별로 걸리는 시간과 모금액을 담은 2차원 배열 travel과 제한시간 K가 주어집니다. 제한시간 안에 서울에서 경산까지 여행을 하며 모을 수 있는 최대 모금액을 return 하도록 solution 함수를 작성하세요.

풀이방법:

동적계획법을 사용해서 풀어야 하는 문제이다. 0번째 인덱스에는 도보로 걸리는 시간, 2번째 인덱스에는 자전거 이동시 걸리는 시간이 담겨 있으며. 1번째, 3번째 인덱스에는 각각 금액이 담겨져 있다. 따라서 0,2번째로 K시간이 넘어가지 않는 선에서 1,3을 더 했을 때 최대가 되는 값을 찾으면 된다.

문제링크:

https://programmers.co.kr/learn/courses/30/lessons/42899

문제:

0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 프로그램을 작성하시오.

덧셈의 순서가 바뀐 경우는 다른 경우로 센다(1+2와 2+1은 서로 다른 경우) 또한 한 개의 수를 여러 번 쓸 수도 있다.

입력:

첫째 줄에 두 정수 N(1<=N<=200),K(1<=K<=200)가 주어진다.

출력:

첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다.

풀이방법:

동적계획법을 사용해서 이 문제를 풀었다. 점화식은 간단하다. K개의 합이 N이 되었을 때, 맨 마지막 수( l )를 빼면 남은 수는 K-1개로 N-l 이 남는 다는 것이다. 그래서 dp 테이블을 다음과 같이 구성할 수 있다.

dp[ i ][ j ] 는 i개의 수를 가지고 합이 j가 되는 경우를 뜻한다. 따라서 처음에는 1로 초기화되며, 한 층이 지날때마다 경우의 수가 더해져 우리가 원하는 dp[k][n]을 구할 수 있다.

문제링크:

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

문제:

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를 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