[백준][C#] 2293 동전 1 - 골드5

문제 보기

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

2293번: 동전 1

 

문제                           

 

입력                          

 

출력                          

 

 

시간 제한	메모리 제한
0.5 초 (추가 시간 없음)	4 MB

 

풀이방법                 

메모리 제한이 이렇게 빡빡할 경우

dp문제인지 의심해 보는 것이 좋다!

 

 

예제 입력 1

3 10
1
2
5

 

 

우선 규칙을 찾아내기 위해

예제를 살펴보며

k가 1부터 4일 때까지만, 어떤 경우의수가 있는지 케이스를 잘게 나눠서 생각해보자.

 

 

 

k = 1

1원짜리 동전이 들어가는 경우 1

 

k = 2

1원짜리 동전만 들어가는 경우는 1, 1

2원짜리 동전도 들어가는 경우는 2

 

k = 3

1원짜리 동전만 들어가는 경우는 1, 1, 1

2원짜리 동전도 들어가는 경우는 1, 2

 

k = 4

1원짜리 동전만 들어가는 경우 1, 1, 1, 1

2원짜리 동전도 들어가는 경우 1, 1, 2 / 2, 2

 

 

 

이쯤 작성하다 보면

점화식을 세울 방법이 떠오르곤 한다.

dp문제에 더 익숙해진다면 문제를 보자마자 알아 챌 것이지만

나와 비슷한 초심자들은 직접 써 보는 것을 추천한다...

 

 

 

더 자세히 쪼갤 수는 없을까?

k = 4의 케이스 경우들을,

2원짜리 동전이 0개, 1개, 2개 들어갈 때로 치환할 수 있을 것 같다.

 

0개 들어갈 경우: 1, 1, 1, 1

1개 들어갈 경우: 1, 1, 2

2개 들어갈 경우: 2, 2

 

 

어? 이거 식으로 쓸 수 있을 것 같은데?

 

 

 

다르게 생각해보면

2원짜리가 0개 들어간 경우는 1원짜리 동전만 사용했을 때 k = 4의 케이스고,

2원짜리가 1개 들어간 경우는 1원짜리 동전만 사용했을 때 k = 2의 케이스고,

 

2원짜리가 2개 들어간 경우는 1원짜리 동전만 사용했을 때 k = 0 (0이 될 케이스는 항상 1이라고 놓고 보자) 아닌가?

 

 

k = 4일 때, 2원짜리 동전을 0개, 1개, 2개 넣을 경우의 식을 세워본다면?

 

// 왜 long인가? 출력 값이 int 범위인 것이지 다른 값들도 int 범위라는 설명은 없다. (이걸로 틀림)
// n개의 동전, 0부터 k까지
long[,] dp = new long[n, k + 1];
dp[2, 4] = dp[1, (4 - 0 * 2)] + dp[1, (4 - 1 * 2)] + dp[1, (4 - 2 * 2)];

 

전체 for문의 코드를 살펴본다.

// 우선 동전들 배열을 오름차순으로 정렬
coins = Sort(coins);

// 메모리가 4mb임을 생각하여, 직전 동전의 dp만 저장하였다.
long[] prevDP = new long[k + 1];
// 0일 때는 무조건 1 (위 설명 참조)
prevDP[0] = 1;

long[] curDP = new long[k + 1];

// 동전을 하나씩 순회
for (int i = 0; i < n; i++)
{
	// 목표치 0원부터 k원까지
	for(int j = 0; j <= k; j++)
	{
    	// 현재 저장 공간 0으로 초기화
		curDP[j] = 0;
        // i가 0개 있는 경우부터 시작한다. j보다 작을 때 까지만.
		for (int count = 0; count <= j; count += coins[i])
		{
        	// 직전 배열에서 (j - (i가 몇 개 있는 경우))일 때 경우의 수를 가져와 더한다. 
			curDP[j] += prevDP[(j - count)];
		}
	}
    	// 현재 배열을 직전 배열로 옮겨준다.
		long[] temp = prevDP;
		prevDP = curDP;
		curDP = temp;
}

 

 

 

전체 코드

using System;

namespace BackjoonCodingTest
{
    internal class Program
    {
        static void Main(string[] args)
        {
            using var reader = new System.IO.StreamReader(Console.OpenStandardInput());
            using var print = new System.IO.StreamWriter(Console.OpenStandardOutput());

            string[] inputs = reader.ReadLine().Split();
            int n = int.Parse(inputs[0]);
            int k = int.Parse(inputs[1]);

            int[] coins = new int[n];
            for(int i = 0; i < n; i++)
            {
                coins[i] = int.Parse(reader.ReadLine());
            }

            coins = Sort(coins);

            long[] prevDP = new long[k + 1];
            prevDP[0] = 1;

            long[] curDP = new long[k + 1];

            for (int i = 0; i < n; i++)
            {
                for(int j = 0; j <= k; j++)
                {
                    curDP[j] = 0;
                    for (int count = 0; count <= j; count += coins[i])
                    {
                        curDP[j] += prevDP[(j - count)];
                    }
                }
                long[] temp = prevDP;
                prevDP = curDP;
                curDP = temp;
            }

            print.WriteLine(prevDP[k]);

            reader.Close();
            print.Close();
        }

        private static int[] Sort(int[] array)
        {
            array = Divide(array, array.Length);

            return array;
        }

        private static int[] Divide(int[] list, int count)
        {
            int harfCount = count / 2;

            int[] divideListLeft = new int[harfCount];
            for (int i = 0; i < harfCount; i++)
            {
                divideListLeft[i] = list[i];
            }

            if (harfCount > 1)
            {
                divideListLeft = Divide(divideListLeft, harfCount);
            }

            int[] divideListRight = new int[count - harfCount];
            for (int i = 0; i < count - harfCount; i++)
            {
                divideListRight[i] = list[harfCount + i];
            }

            if (count - harfCount > 1)
            {
                divideListRight = Divide(divideListRight, count - harfCount);
            }


            return Merge(divideListLeft, divideListRight, divideListLeft.Length, divideListRight.Length);
        }

        private static int[] Merge(int[] leftList, int[] rightList, int leftListCount, int rightListCount)
        {
            int[] list = new int[leftListCount + rightListCount];

            int leftIndex = 0;
            int rightIndex = 0;
            int mergeIndex = 0;
            while (leftIndex < leftListCount && rightIndex < rightListCount)
            {
                if (leftList[leftIndex] < rightList[rightIndex])
                {
                    list[mergeIndex++] = leftList[leftIndex++];
                }
                else
                {
                    list[mergeIndex++] = rightList[rightIndex++];
                }
            }

            while (leftIndex < leftListCount)
            {
                list[mergeIndex++] = leftList[leftIndex++];
            }

            while (rightIndex < rightListCount)
            {
                list[mergeIndex++] = rightList[rightIndex++];
            }

            return list;
        }
    }
}

 

뒤의 병합 정렬 메서드는 개인적으로 정렬이 필요할 때마다 사용하고 있으니 참고 바란다.

정렬하는 코드를 제외하면 전체 길이는 짧은 편이다.