[홀로 하는 코딩 공부] 1,2,3 더하기 4(Python)

백준

사용 언어: Python

문제 링크: https://www.acmicpc.net/problem/15989

15989번: 1, 2, 3 더하기 4

 

 

*** 본 문제를 푸는 과정을 공유하려 한다.

---

▶ 처음에 이 문제를 보자마자 조합문제일까 생각해보았지만, n의 개수가 10,000보다 작거나 같다는 조건을 보고 dp문제일 것 같다는 생각이 들었다. 그래서 규칙을 찾고자 우선 5정도까지 다 작성해보았다.

 

▶ 이렇게까지 작성해보고 n 값이 그 값을 만들 수있는 방법의 수 인가 생각이 들었다. 그래서 마저 8까지 작성해보았다.(10까지 해보려했는데 숫자가 많아져서 8까지만 해보았다..)

 

 

▶ 10까지 작성해본 결과, 위의 혹시나 하는 가정은 완전히 틀린것임을 알 수 있다. 8까지 작성한거에 한해서 규칙을 찾아보기 위해 작성한 것을 살펴보았다. 보다보니, 숫자 조합이 아래와 같은 종류임을 알 수 있다.

• (1)로만 이루어진 경우의 수
• (1,2)로만 이루어진 경우의 수 + (2)로만 이루어진 경우의 수
• (1,3)으로만 이루어진 경우의 수 + (3)로만 이루어진 경우의 수
• (2,3)으로만 이루어진 경우의 수 + (1,2,3)으로만 이루어진 경우의 수

▶ 위의 종류대로 해당하는 경우에 다른 색상을 이유하여 칠해보았다.

▶ 칠한 색상 각각의 개수와 총합의 개수를 구해보았다.

 

▶ 색상대로 규칙이 있는것을 확인할 수 있다.

• (1)로만 이루어진 경우의 수
  • n값이 어떠한 값이던 상관없이 무조건 1이다.
• (1,2)로만 이루어진 경우의 수 + (2)로만 이루어진 경우의 수
  • n=2,3인 경우는 1개, n=4,5인 경우는 2개, ... 즉, 개수는 n//2개 이다.
• (1,3)으로만 이루어진 경우의 수 + (3)로만 이루어진 경우의 수
  • n=3,4,5인 경우는 1개, n=6,7,8인 경우는 2개, ... 즉, 개수는 n//3개이다.
• (2,3)으로만 이루어진 경우의 수 + (1,2,3)으로만 이루어진 경우의 수
  • n=5,6인 경우는 1개, n=7인 경우는 2개, n=8인 경우는 3개, ... 규칙이 보이지 않는다.
  • 더 상세히 분석하기 위해, n=11인것까지 구해본다.
  • 10까지 1,2,3,4,5 순차적으로 가다가 11부터 갑자기 2가 증가해서 7이 되는 것을 보니 순차적으로 증가하는 것도 아니다.
  • 그런데 자세히 보면 총합개수를 이용한 규칙이 있는 것을 확인 할 수 있다. 구하고자 하는 n값에서 5를 뺀 값에 해당하는 방법의 총 수가 초록색 값임을 확인할 수 있다. 단, 초록색 값이 0이 아닌 값이 생기는 n인 5부터 해당이 된다. 즉, dp[i] = dp[i-5]인 것이다.

 

▶ 위의 규칙대로 코드를 작성하면 아래와 같고, 통과다!!

import sys
input = sys.stdin.readline

T = int(input())
MAX_VALUE = 10001
dp = [1]*MAX_VALUE
dp[2] = 2

for i in range(3, MAX_VALUE):
    dp[i] += (i//2 + i//3)
    if i >= 5:
        dp[i] += dp[i-5]
for _ in range(T):
    n = int(input())
    print(dp[n])

 

 

 

▶ 일전에 풀었던 문제인데, 풀이 방법을 정리하려다 보니 뜻하지 않게 시간이 소요되었다.

▶ 원래 해당 문제를 풀 때, 8까지 모든 조합을 다 적어봤는데 풀리지 않아서 고민하다가 중간에 막혀서 다른 풀이를 봤지만, 다양한 풀이를 보았다. 그런데 내가 봤던 다양한 풀이법들이 풀이 과정이 이해가 되지않았다. 이러한 방법들을 익힌다면 다음에 이런 문제가 나오면 스스로 못 풀 것 같다는 생각이 들어서 일전에 혼자 했던 나만의 방법을 다시 진행해보았더니 풀렸다.

 

---

>> 위 내용은 필자가 코딩테스트 문제를 푼 코드입니다.

>> 부족한 점이 많을 수 있기에 잘못된 내용이나 궁금한 사항이 있으면 댓글 달아주시기 바랍니다.

>> 긴 글 읽어주셔서 감사합니다.