글 읽기 - 반복문 순서에 대한 질문

d252b 6년 전 0

예를 들어, 1원짜리, 5원짜리, 7원짜리 동전이 있다고 하고, x원을 만드는 경우의 수는

dp[x] = dp[x-1] + dp[x-5] + dp[x-7]

이런식으로 풀 수 있다고 알고 있습니다.

그래서 이 문제도 위의 방식을 이용하여 풀었는데요,

만들고자 하는 금액(=money) 과 동전의 금액(=coin[index]) 라 할 때,

dp[money] +=dp[money-coin[index++]] 라고 생각을 하였습니다.

그러나 아래 코드에서 27번~33번 라인에서

주석처럼 for문의 순서가 바꾸어서 짰는데 틀렸었습니다.

왜 coin[index]가 바깥 포문이고, money 포문이 내부 포문인가요?

고민을 해 봐도 잘 납득이 되지 않네요.

#include <iostream>
#include <vector>

using namespace std;
vector<int> arr;
int T;
int dp[10010];

int main()
{

	scanf("%d", &T);
	while (T--)
	{
		fill_n(dp, 10010, 0);
		int num;
		scanf("%d", &num);
		arr.resize(num + 1, 0);
		for (int i = 1; i <= num; i++)
		{
			scanf("%d", &arr[i]);
		}
		int money; 
		scanf("%d", &money);
		
		dp[0] = 1;
		for (int i = 1; i <= num; i++)   
		{
			for (int j = arr[i]; j <= money; j++)
			{
				dp[j] += dp[j - arr[i]];
			}
		}
        // 왜 아래 for문처럼 하면 안될까요?
        /* 
        for (int i = 1; i <= money; i++)
		{
			for (int j = 1; j <= num; j++)
			{
				if (i - arr[j]>=0)
					dp[i] += dp[i - arr[j]];
			}
		}
        */

		printf("%d\n", dp[money]);
	}
}

happyleeyi 6년 전 0

주석처럼 하면 예를 들어 동전이 1, 3, 5가 있다 하면

1을 만들 땐 1가지 (1)

2를 만들 땐 1가지 (1,1)

3을 만들 땐 2가지 (1,1,1)(3)

4를 만들 땐 2가지 (1,1,1,1)(1,3)

5를 만들 땐 3가지 (1,1,1,1,1)(1,1,3)(5)

주석처럼 할 시에

5만들 때 = 4만들 때 + 2만들 때 + 0만들 때(1) = 2+1+1 로 4가 나와 오답입니다.

잘 보면 4에서 1을 각 더하면 (1,1,1,1,1)(1,1,3)이 나오고

2에서 3을 각 더하면(1,1,3)이 나오고

0에서 5를 더하면 (5)가 나옵니다.

따라서 (1,1,3)이 겹치는게 보이죠.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

반복문 순서에 대한 질문

d252b 6년 전 0

happyleeyi 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말