Easy is Perfect

[백준] 9095번 1, 2, 3 더하기 _ 문제 풀이

  • melonicedlatte
  • Apr 09, 2021


1. 문제

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

2. 풀이

2.1. 내 풀이

dfs 를 이용하여 문제를 해결해주었습니다. 방문한 곳은 visited 배열로 표기하여 사용한 숫자를 체크하였고, 이후 reduce를 이용하여 사용한 숫자의 배치 가능한 개수를 구했습니다(예_ 1,2,3,3 은 4!/2! ).

from functools import reduce
def val(n, n_1, n_2, n_3):
    global is_visited, answer
    if is_visited[n_1][n_2][n_3]:
        return
    is_visited[n_1][n_2][n_3] = True
    if n < 0:
        return
    elif n == 0:
        answer += reduce(lambda x, y : x*y, list(range(1, n_1+n_2+n_3+1))) / reduce(lambda x, y : x*y, list(range(1, n_1+1 if n_1 else 2))) / reduce(lambda x, y : x*y, list(range(1, n_2+1 if n_2 else 2))) / reduce(lambda x, y : x*y, list(range(1, n_3+1 if n_3 else 2)))
        return
    val(n - 1, n_1 + 1, n_2, n_3)
    val(n - 2, n_1, n_2 + 1, n_3)
    val(n - 3, n_1, n_2, n_3 + 1)

N = int(input())
for _ in range(N):
    answer = 0
    is_visited = [[[False for ___ in range(12)] for __ in range(12)] for _ in range(12)]
    val(int(input()), 0, 0, 0)
    print(int(answer))

2.2. DP를 이용한 풀이

arr[n] 안에는 n 숫자를 합으로 나타낼 수 있는 가능한 값을 저장하는 공간입니다. 새로운 n을 갱신하려면 arr[n-3], arr[n-2], arr[n-1] 의 값을 사용해야합니다.

예를 들어, arr[4]를 갱신하려면, arr[1] (1까지 가능한 합의 개수) 3을 추가한 경우 + arr[2] (2까지 가능한 합의 개수)에서 2를 추가한 경우 + arr[3] (3까지 가능한 합의 개수)에서 1를 추가한 경우의 케이스가 있습니다. 이런 식으로 1씩 값을 올리면서 값을 갱신해주면 쉽게 답을 구할 수 있습니다.

arr=[0,1,2,4]
for i in range (4,11):
  arr.append(sum(arr[-3:]))
for _ in range(int(input())):
  print(arr[int(input())])



Search