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

Adela·2020년 7월 28일
0

백준온라인저지

목록 보기
38/53
post-thumbnail

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 배열의 길이를 출력한다.

이렇게 풀었는데, 수학적(?)으로 더 쉬운 방법이 있었다.
다른 사람의 풀이를 보니, 해당 테스트케이스를 [테스트케이스-3] + [테스트케이스-2] + [테스트케이스-1]
이런식으로 구하면 되더라.. 계산 방식을 몰라 복잡하게 푼 것 같다.. ㅜㅜ

profile
개발 공부하는 심리학도

0개의 댓글