[9095/Swift] 1, 2, 3 더하기

*** 언어는 Swift! ***

 

이번에도 DP를 이용한 문제인 1, 2, 3 더하기 라는 문제였다. 이번 문제는 규칙을 찾아야하는 문제였기 때문에 머리가 조금 아팠다.

아직 알고리즘을 푸는데 익숙하지 않아서 그런가 이런 규칙을 찾는 것 또한 나에게는 많은 시간이 필요한 일이었기 때문에 도저히 안되겠어서 블로그의 힘을 빌렸다...🥲

 

이번 문제는 9095번의 1, 2, 3 더하기 문제이다 자세한 내용은 아래와 같다.

역시나 이번 문제도 DP 문제인 만큼 규칙을 열심히 찾아보려고 노력했으나 내 짧은 뇌로는 역부족이었다.

그래서 다른 사람들의 블로그를 참고하면서 내 나름대로 열심히 규칙을 이해해보려고 노력했다.

그렇게 이해한 게 아래와 같은 방법이었다.

 

일단 1과 2, 3 이렇게 세 숫자만을 이용해야하기 때문에 3까지의 가짓수를 구한다. 

그리고 세 숫자의 가짓수를 이용해 3 이후의 숫자들의 가짓수를 구한다.

 

정수가 1일 때 만들 수 있는 가짓수는 1개이다 (1)

정수가 2일 때 만들 수 있는 가짓수는 2개이다 (1+1, 2)

정수가 3일 때 만들 수 있는 가짓수는 4개이다 (1+1+1, 2+1, 1+2, 3)

 

정수가 4일 때 만들 수 있는 가짓수는 아래와 같다. (4 + 2 + 1 = 7)

• 1로 4를 만드려면 3이 필요하다 (1 + 3 = 4) 3을 만들 수 있는 가짓수는 4개이다.
• 2로 4를 만드려면 2가 필요하다 (2 + 2 = 4) 2를 만들 수 있는 가짓수는 2개이다.
• 3로 4를 만드려면 1이 필요하다 (3 + 1 = 4) 1을 만들 수 있는 가짓수는 1개이다.

위와 같은 방법으로 이번에는 5를 만들어보자.

정수가 5일 때 만들 수 있는 가짓수는 아래와 같다. (7 + 4 + 2 = 13)

• 1로 5를 만드려면 4가 필요하다 (1 + 4 = 5) 4를 만들 수 있는 가짓수는 7개이다.
• 2로 5를 만드려면 3이 필요하다 (2 + 3 = 5) 3을 만들 수 있는 가짓수는 4개이다.
• 3로 5를 만드려면 2가 필요하다 (3 + 2 = 5) 2를 만들 수 있는 가짓수는 2개이다.

이런식으로 만들다보면 규칙이 하나씩 보이기 시작한다.

4일때는 이용하는 숫자가 3, 2, 1 이고 5일때는 이용하는 숫자가 4, 3, 2 이다. 그리고 6일때는 5, 4, 3 일 것이다.

하나씩 증가하는 것을 볼 수 있다.

 

이렇게 나온 규칙으로 식을 만들자면 dp(n) = dp(n - 1) + dp(n - 2) + dp(n - 3) 일 것이다.

대입해보면 알 수 있다. 

dp(4) = dp(3) + dp(2) + dp(1) 즉 이 말은 dp(4) = 4 + 2 + 1 인 셈이다.

 

그럼 식을 구했으니 문제를 쪼개보자.

 

1. 첫째 줄에 테스트 케이스 갯수 T가 주어지며, T 갯수 만큼 n이 주어진다.

2. 1부터 3까지의 갯수를 미리 저장해둔다.

3. dp(n) = dp(n - 1) + dp(n - 2) + dp(n - 3) 를 이용해 가짓수를 구한다.

 

1. 첫째 줄에 테스트 케이스 갯수 T가 주어지며, T 갯수 만큼 n이 주어진다.

let t = Int(readLine()!)!

var testCaseArray: [Int] = []

for _ in 0..<t {
    // 정수 n이 주어진다
    let n = Int(readLine()!)!
    testCaseArray.append(n)
}

T를 입력받고 T의 갯수만큼 N을 입력받은 후 배열에 저장해둔다.

 

2. 1부터 3까지의 갯수를 미리 저장해둔다.

1부터 3까지는 가짓수를 구할 수 있으니 미리 배열에 저장해둔다.

 var numberArray: [Int] = [1, 2, 4]

 

3. dp(n) = dp(n - 1) + dp(n - 2) + dp(n - 3) 를 이용해 가짓수를 구한다.

n이 11보다 작다고 명시되어있기 때문에 1부터 3까지의 가짓수를 제외한 4부터의 11까지의 가짓수를 구한다.

for i in 3..<10 {
    let cal = numberArray[i - 1] + numberArray[i - 2] + numberArray[i - 3]
    numberArray.append(cal)
}

그리고 저장된 n의 순서대로 값을 출력한다.

for i in 0..<testCaseArray.count {
    print(numberArray[testCaseArray[i] - 1])
}

testCaseArray[i] - 1을 한 이유는 배열이 0부터 시작되기 때문이다!

 

이렇게 규칙을 찾는게 어려웠던 한 번 규칙이 보이니까 다음부터 계속 잘 보여서 재미있게 풀었던 것 같다!

오늘도 한 건 해결!