백준알고리즘 2293번 동전 1 C#

세부 정보

• 사이트: 백준알고리즘
• 번호: 2293
• 문제명: 동전 1
• 언어: C#
• 분류: 다이나믹 프로그래밍
• 비고: 

 

문제

n가지 종류의 동전이 있다. 각각의 동전이 나타내는 가치는 다르다. 이 동전을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그 경우의 수를 구하시오. 각각의 동전은 몇 개라도 사용할 수 있다.

사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다.

 

입력

첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다.

 

출력

첫째 줄에 경우의 수를 출력한다. 경우의 수는 2^31보다 작다.

 

풀이

보완 설명 필요

// 텍스트 파일을 전문을 입력하는 역할을 맡는다.
using StreamReader streamReader = new StreamReader(new BufferedStream(Console.OpenStandardInput()));
// 텍스트 파일을 전문으로 출력하는 역할을 맡는다.
using StreamWriter streamWriter = new StreamWriter(new BufferedStream(Console.OpenStandardOutput()));
// 동전의 종류 수와 가치의 합을 공백으로 구분해 입력받아 정수 배열로 저장한다.
int[] input = Array.ConvertAll(streamReader.ReadLine().Split(),int.Parse);
// 개별 동전의 가치를 저장한다.
int[] coin = new int[input[0] + 1];

// 개별 동전의 가치를 입력받아 저장한다.
for (int i = 1; i <= input[0]; i++)
    coin[i] = Convert.ToInt32(streamReader.ReadLine());

// 코인의 목표 가치 달성 경우의 수를 저장하는 이차원 배열 생성
// 배열 대괄호 콤마 앞은 코인의 종류(행), 뒤는 코인의 총 가치(열)를 의미한다
int[,] coinCase = new int[input[0] + 1, input[1] + 1];

// 행 값과 무관하게 0번째 열은 무조건 1을 채운다.
for (int i = 1; i <= input[0]; i++)
    coinCase[i, 0] = 1;

// 행은 입력한 동전의 종류 수만큼 반복
for (int i = 1; i <= input[0] ; i++)
{
    // 열은 총 가치만큼 반복
    for(int j = 1; j <= input[1]; j++)
    {
        // 총 가치값이 동전의 가치보다 크거나 같다면
        if (j >= coin[i]) 
            coinCase[i, j] = coinCase[i - 1, j] + coinCase[i, j - coin[i]];
        else 
            coinCase[i, j] = coinCase[i - 1, j];
    }
}

// 동전의 목표 가치 달성이 가능한 경우의 수를 출력한다
streamWriter.Write(coinCase[input[0], input[1]]);
// 개체와 내부 스트림을 닫고 입력 시스템 리소스 해제
streamReader.Close();
// 개체와 내부 스트림을 닫고 출력 시스템 리소스 해제
streamWriter.Close();

 

후기

이것도 StreamReader와 StreamWriter를 사용했다. 현재까지 다이나믹 프로그래밍은 제한시간 내에 풀기가 어려운 문제가 많았다. 할 수 있는 것은 반복적인 피드백과 반복 풀이와 기술 문서 조사가 최선이다. 다이나믹 프로그래밍에 언제쯤 익숙해지려면 앞에 나열한 방법 외에도 무엇이 있는지 찾고 싶다.