[코딩테스트]백준 - 1, 2, 3 더하기 (9095번)

Adela·2020년 7월 28일

123더하기 JavaScript 다이나믹프로그래밍 백준 알고리즘 자바스크립트 코딩테스트

백준온라인저지

목록 보기

38/53

1,2,3 더하기

문제

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.

1+1+1+1

1+1+2

1+2+1

2+1+1

2+2

1+3

3+1

정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다.

출력

각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다.

예제 입력 1
3
4
7
10
예제 출력 1
7
44
274
출처

ICPC > Regionals > Asia Pacific > Korea > Asia Regional - Taejon 2001 PC번

문제를 번역한 사람: baekjoon

문제의 오타를 찾은 사람: standardraccoon wjrqur1200

알고리즘 분류

다이나믹 프로그래밍

해결한 코드

var fs = require('fs');
var input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');
// var input = fs.readFileSync(__dirname + '/stdin.txt').toString().replace(/\r/g, "").trim().split('\n');

var testCases = makeInputNumber()
var dp = []
dp = calculateDp(dp)
var answer = dp[testCases[0]].length+""
for (var i = 1; i < testCases.length; i++) {
    var testCase = testCases[i]
    answer += "\n" + dp[testCase].length+""
}
console.log(answer.trim())

function makeInputNumber() {
    var ns = []
    for (var i = 1; i < input.length; i++) {
        ns.push(input[i] / 1)
    }
    return ns
}

function calculateDp(dp) {
    dp[0] = []
    dp[1] = ['1']
    dp[2] = ['1 1', '2']
    dp[3] = ['1 1 1', '1 2', '2 1', '3']
    for (var i = 4; i < 12; i++) {
        var withOne = combination(dp[1], dp[i - 1])
        var withTwo = combination(dp[2], dp[i - 2])
        var withThree = combination(dp[3], dp[i - 3])
        var result = mergeThreeArraies(withOne, withTwo, withThree)
        dp[i] = result
    }
    return dp
}

function mergeThreeArraies(one, two, three) {
    two.push(...three)
    one.push(...two)
    var mergedResult = new Set(one)
    return [...mergedResult]
}

function combinePartially(oneArray, theOtherArray) {
    var candidates = []
    var current = ''
    var candidate = ''
    for (var i = 0; i < oneArray.length; i++) {
        current = oneArray[i]
        for (var j = 0; j < theOtherArray.length; j++) {
            candidate = current + ' ' + theOtherArray[j]
            candidates.push(candidate)
        }
    }
    return candidates
}

function combination(oneArray, theOtherArray) {
    var combinatedResult = combinePartially(oneArray, theOtherArray)
    combinatedResult.push(...combinePartially(theOtherArray, oneArray))
    var resultBySet = new Set(combinatedResult)
    return [...resultBySet]
}

풀이

※ 다이나믹 프로그래밍 알고리즘 사용

1. 규칙을 찾는다.

0 -> 없음

1 -> 1

2 -> 1+1, 2

3 -> 1+1+1, 1+2, 2+1, 3

4 -> 1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 1+3, 3+1, 2+2

여기서 4를 한번 뜯어보자.

1+1+1+1
👉🏻 1의 1 + 3의 1+1+1 || 3의 1+1+1 + 1의 1 || 2의 1+1 + 2의 1+1

1+1+2
👉🏻 1의 1 + 3의 1+2

1+2+1
👉🏻 1의 1 + 3의 2+1

1+3
👉🏻 1의 1 + 3의 3

2+1+1
👉🏻 3의 2+1 + 1의 1

3+1
👉🏻 3의 3 + 1의 1

2+2
👉🏻 2의 2 + 2의 2

그런데 4-1=3, 4-2=2, 4-1=3이다.
즉, 테스트케이스 4에 대한 답을 구하려면, 테스트 케이스 1, 3의 조합, 2, 2의 조합, 3, 1의 조합을 구한 다음 중복을 제외하고 모두 합치면 된다.
만약 테스트케이스 11에 대한 답을 구한다면? 테스트케이스 1, 10 && 10, 1, 2, 8 && 8, 2, 3, 7 && 7, 3의 조합을 각각 구한 다음, 중복을 제외하여 모두 합치면 된다.

2. 각 테스트케이스에 대한 답을 저장할 배열을 만든다.

나는 dp배열을 만들었다.
이 배열에다가 위에서 구한 테스트케이스 결과값들을 저장할 것이다.

3. dp를 구할 함수를 만든다.

참고로 함수는 기능별로 각각 나누는 것이 좋다고 하여, 나는 다음과 같은 함수들을 만들었다.

입력으로 받은 값을 숫자로 테스트케이스용 숫자로 바꾸는 함수

dp를 구하는 함수

(dp를 구하기 위해) 조합을 구하는 함수

(조합을 구하기 위해) 부분 조합을 구하는 함수
"2, 8 && 8, 2"와 같이 순서를 바꿔서도 조합을 구하기 위해 따로 뺌

구한 조합 값들을 (중복을 제외시켜) 합치는 함수

4. 입력으로 들어온 각 테스트케이스에 대한 dp 배열의 길이를 출력한다.