티바이트

문제 링크 (알고스팟)
https://algospot.com/judge/problem/read/ASYMTILING

문제 이해

2 x n크기의 직사각형 공간을 2x1혹은 1x2 크기의 타일로 완전히 채우는 방법의 수를 구하는 문제이다.

타일의 배치가 좌우대칭인 것은 제외한다.

풀이

예를 하나 뽑아서 2 x 6 크기의 공간을 채우는 경우를 생각해 본다.

여기서 2 x 6 크기의 공간을 채우는 여러 경우들을 2가지로 나눌 수 있다.

A. 맨 마지막 타일이 세로로 되어 있음

B. 맨 마지막 타일이 가로로 2개 되어 있음

남은 부분의 크기를 보면,

A의 경우 나머지 공간의 너비는 5이고

B의 나머지 공간의 너비는 4이다.

즉, A에서 남은 부분을 채우는 방법의 수는, 이 문제에서 너비가 5인 공간을 채우는 경우의 답과 같다.

B의 나머지 부분을 채우는 방법의 수 역시 너비가 4인 공간을 채우는 경우의 답과 같다.

여기서 이 문제의 재귀적 속성을 발견할 수 있으며

이 문제를 Dynamic Programing (동적 계획법)으로 풀 수 있다는 것을 알 수 있다.

상향식(bottom-up)으로 어떻게 풀 지를 구체적으로 생각해 보면,

- n=1 일 때 (1 가지)

- n=2 일 때 (2 가지)
- n=3 일 때는  (n=2의 가지수) + (n=1의 가지수)

'n=2의 가지수'는 위 그림에서 A의 경우이고, 'n=1의 가지수'는 위 그림에서 B이다.

- n=4일 때는 (n=3)의 가지수 + (n=2의 가지수)

...

...

..

n = k일 때는 (n=k-1 의 가지수) + (n=k-2 의 가지수)

어디서 본 적이 있는 점화식이 나온다. 바로 피보나치 수열이다.

그런데 문제에서 좌우대칭인 경우는 제외하라는 조건이 있다.

이번에는 채워야 할 공간의 크기가 짝수인 것과 홀수인 것으로 나누어 생각해야 한다.

공간의 크기가 홀수일 때 좌우대칭이 되기 위한 조건은

가운데에 블록이 세로로 있어야 하며 분할된 한 쪽 너비는 (int)n/2이다.

공간의 크기가 짝수일 때는 분할된 한 쪽 너비가 n/2이다.

분할된 너비에 해당하는 경우의 수를 빼면 최종적인 답을 구할 수 있다.

구현

대칭인 경우를 제외시키기 위해 너비의 절반을 구해야 하는데,

피보나치 수열을 구하는 과정에서 같이 계산하도록 했다.

그리고 답을 리턴할 때, 이 문제에서 나머지연산한 결과를 요구하므로

계산 과정에서 그 수를 초과하지 않도록 주의하여야 한다.

A - B%mod + mod 와 같이 더해주면 값이 음수가 되는 것을 방지할 수 있다.

문제 링크 : https://www.algospot.com/judge/problem/read/POTION

(알고스팟)

문제 이해

어떤 약을 한 단위 만드는 데 필요한 n개의 재료들의 양과

현재 넣은 재료의 양이 입력된다.

이 때 약을 만들기 위해 더 넣어야 하는 재료들의 양을 구하는 문제이다.

입력값은 모두 정수이고,

약을 최소한 1단위 이상은 만들어야 한다.

풀이

완성한 약의 양이 꼭 정수단위일 필요가 없다는 점에 주의해야 한다.

따라서 필요한 재료들의 양을 최대공약수로 나누어

들어가야 하는 재료들의 비를 구했다.

예를 들어 들어가야 하는 3가지 재료의 양이 각각 2 4 6 이라면

최대공약수 2로 나누어 1 2 3 라는 비율을 구한다.

이제 들어가야 하는 재료의 양은 1 2 3 의 정수배인

1 2 3

2 4 6

3 6 8

4 8 10

...

...

과 같이 된다.

(정수배인 이유는 입력되는 재료의 양이 정수이므로)

그런데 문제에서 완성 약을 한 단위 이상 만들어야 한다는 조건이 있으므로

2 4 6 다음부터 검사하면 되는것이다.

여기서 현재 넣은 재료가 3 6 7 이라면

재료추가로 만들 수 있는 값이 위 정수배들 중에서 3 6 8 이므로

약을 완성시키기 위해 0 0 1 만큼의 재료를 더 넣어야 하는 것이다.

최대공약수를 구하는 부분은 유클리드 알고리즘을 사용하였고,

n개 수의 GCD를 구하기 위해 해당 알고리즘을 n-1번 반복하였다.

(관련글 : http://www.tibyte.kr/224)

코드

#include <cstdio>

#include <cmath>

using namespace std;

//GCD계산 (유클리드)

int calcGcd(int n1, int n2)

{

int temp;

if (n1 < n2) {

temp = n1;

n1 = n2;

n2 = temp;

}

while (n2 != 0) {

temp = n1%n2;

n1 = n2;

n2 = temp;

}

return n1;

}

int main(void)

{

int numTry;

scanf("%d",&numTry);

while (numTry--)

{

int numElem;

scanf("%d",&numElem);

int *ideal = new int[numElem];

int *curr = new int[numElem];

int gcd;

double curMul = 0;

double maxMul = 0;

int mul;

//비율값 입력받음

for (int i = 0; i < numElem; i++) 

scanf("%d", &ideal[i]);

//비율값의 gcd계산

gcd = ideal[0];

for (int i = 1; i < numElem; i++) 

gcd = calcGcd(gcd, ideal[i]);

//ideal값 재계산

for (int i = 0; i < numElem; i++)

ideal[i] = ideal[i]/gcd;

//현재넣은값 입력받음

for (int i = 0; i < numElem; i++) {

scanf("%d", &curr[i]);

curMul = (double)curr[i] / ideal[i];

if (curMul >maxMul ) maxMul = curMul;

}

mul = ceil(maxMul);

for (int i = 0; i < numElem; i++) {

ideal[i] *= mul;

printf("%d ", ideal[i] - curr[i]); 

}

printf("\n");

}

return 0;

}