백준 1679-숫자놀이

다이나믹

 

---

1679번: 숫자놀이

<알고리즘 생각하기>

 

동적계획법 = 다이나믹을 사용하는 문제인 것을 알아차리기!

예제를 통해서 보면 1과 3을 사용하고 사용하는 횟수가 5번이 넘어갈 때 그 숫자를 출력하는 것이다.

이때, 1부터 1씩 증가해 숫자를 만들 때 1과 3을 사용해야하고 그 횟수를 계속 기록한다는점에서 기록한 횟수를 재사용하는 것인가?를 생각해보았고, 이를 통해 다이나믹 문제임을 파악할 수 있었다.

 

1. while문을 돌려 만들려고 하는 숫자를 계속 늘려준다.

이때, array[만들려고 하는 수]가 횟수제한을 뛰어넘을 경우 그 때의 [만들려고 하는 수]를 출력해주고 break

 

2. s[]배열에 입력 순서대로 숫자가 저장된다.

n개를 입력받으면 s[0]~s[n-1] 배열에 입력받은 숫자 a가 저장되어있고 array[a]에는 숫자의 사용횟수가 들어가기에, 처음 입력받은 수는 무조건 1이다.

 

3. 다이나믹 사용

while문을 통해 i를 증가시키는데, array[i]에는 초기값 0이 들어있다.

- 0일때 : 무조건 값이 들어간다.

- 0이 아닐때 : 작은 값이 들어간다.

ex) 6을 만들 때 : 3+3 => 2번, 1+1+1+1+1+1=6 =>6번 // 2번이 들어가야함

---

 

<예제 설명>

1,3을 사용해 숫자를 만들어야한다.

array[i]에는 i번째 숫자를 만들기 위해 필요한 최소한의 숫자가 들어간다.

 

scanf후 array의 구성

1	2	3	4	5	6	7	8	9	10
1	0	1	0	0	0	0	0	0	0

 

while문에서 i==1일때

1에서 1과 3을 (더해서)사용해 만들 수 있는 숫자

1+1=2(2번의 숫자사용)  => 2번(array[1](1번) + array[1](1번))

1+3=4(2번의 숫자사용) =>  2번(array[1](1번) + array[3](1번))

1	2	3	4	5	6	7	8	9	10
1	1	1	1	0	0	0	0	0	0

while문에서 i==2일때

2에서 1과 3을 (더해서)사용해 만들 수 있는 숫자

2+1=3(2번의 숫자사용)  => 2번(array[2](array[2]를 만들기 위한 최소한의 수 :1번) + array[1](1번))

%단, array[3]은 3번을 한번 사용해 만들 수 있다/ (array[3]=1)이기때문에/ 따라서 array[3]은 1로 그냥 둠.

2+3=5(2번의 숫자사용) =>  2번(array[2](array[2]를 만들기 위한 최소한의 수 :1번) + array[3](1번))

1	2	3	4	5	6	7	8	9	10
1	1	1	1	2	0	0	0	0	0

....

이러한 과정을 while문을 통해서 계속 진행하고 array[i]의 값이 n을 넘을 경우를 출력한다.

 

4. 따라서 14일때가 5번을 넘게 되기때문에 홀순이가 이기며 4를 같이 출력한다.

---

#include <stdio.h>

int array[1020] = { 0 };
int s[1020];

int main()
{
	int n;
	scanf("%d", &n);
	int a;
	for (int i = 0; i < n; i++)
	{
		scanf("%d", &a);
		array[a] = 1;
		s[i] = a;
	}

	int lim;
	scanf("%d", &lim);

	int i= 1;
	int k = 0;
	while (1)
	{
		for (int j = 0; j < n; j++)
		{
			if (array[s[j]] + array[i] < array[s[j] + i] || array[s[j] + i] == 0)
			{
				array[i + s[j]] = array[s[j]] + array[i];
		
			}
		}
		
		if (array[i] > lim)
		{
			if (i % 2 == 0)
			{
				printf("holsoon win at %d", i);
				
			}
			else
			{
				printf("jjaksoon win at %d", i);
			}
			break;
		}

		i++;
	}
}