아주 쉬운 dp알고리즘을 백트래킹으로 푼 나.. [백준]9095 (파이썬

https://www.acmicpc.net/problem/9095

9095번: 1, 2, 3 더하기

위 문제는 숫자 1,2,3으로 특정 숫자를 만들 수 있는 경우의 수를 구하는 문제이다.

 

예를들어 4라면

• 1+1+1+1
• 1+1+2
• 1+2+1
• 2+1+1
• 2+2
• 1+3
• 3+1

총 7개가 된다.

 

이 문제는 다이나믹 프로그래밍으로 분류가 된다. 

 

1,2,3으로 만들어야 하는 숫자가 n이라 해보자.

n = 1 일때는 1

n = 2 일때는 2

n = 3 일때는 4

n = 4 일때는 7

 

n = 4인 경우는 n이 1일 때와 2일 때와 3일때를 더한 경우와 같다.

 

따라서 아래와 같은 점화식을 유도할 수 있고 코드는 매우 간결해지며 쉽다!

d[n] = d[n-1] + d[n-2] + d[n-3] (n은 4이상 11 미만인 수)

 

하지만 나는 이따구로 풀지 않았다. 당연히 위의 방식도 생각했지만 고작 저 방법으로 풀기 싫었달까.. 저 방법이 아니고서는 dp로 풀 방법이 생각나지 않았다. 그래서 백트래킹으로 풀었다. 왜냐하면 탐색을 하는데 특정 조건이 있기 때문이다.

def backTracking(_sum,n):
  global case
  if _sum == n:
    case+=1
    return
  elif _sum > n:
    return
  else:
    for i in range(1,4):
      backTracking(_sum+i,n)

t = int(input())
for _ in range(t):
  case=0
  n = int(input())
  backTracking(0,n)
  print(case)

공부에 도움은 많이 되었다.

 

글을 쓰는 도중 생각난건데 내 코드는 남들이 보면 괜히 쉬운코드도 어렵게 보일것같다. 아직 그런 것을 생각하고 코딩을 하지는 않는다. 결과물만 제대로 나온다면 어떠하든 상관없다. 

 

학교 교수님께서 강의시간에 코딩은 아트라고 했다. 내가 쓴 코드가 하나의 결과물을 위한 부속품일 뿐이고 코드로 인한 섬세한 영향을 생각하지 않았다면 그건 아트가 아니라 싸구려이다. 좀 더 코드에 마음을 담아보자.