9095번: 1, 2, 3 더하기

문제 접근 🤔

• DFS로 접근하여 풀면 간단한 문제
• 정수 n 과 1, 2, 3 조합으로 더한 합이 같아질 때가 원하는 경우이다.
• 재귀함수를 돌면서 n - (1, 2, 3 조합으로 더한 합) == 0 이 되면 경우의 수 cnt 를 1 씩 올려준다.
• DFS 함수의 리턴 값으로 cnt 를 반환하면 끝
  
  
  

놓쳤던 부분 😅

• 없음
  
  
  

코드 😁

파이썬 코드(40 ms)

def dfs(N, cnt = 0):
    for i in range(1, 4):
        cnt = dfs(N - i, cnt) if N - i > 0 else cnt + 1 if N - i == 0 else cnt
    return cnt

T = int(input())
for _ in range(T):
    n = int(input())
    print(dfs(n))

자바스크립트 코드(120 ms)

const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : __dirname + '/input.txt';
const [L, ...datas] = fs.readFileSync(filePath).toString().trim().split('\n').map(Number);

const dfs = (N, cnt = 0) => {
  for (let i = 1; i <= 3; i++) {
    cnt = N - i > 0 ? dfs(N - i, cnt) : N - i === 0 ? cnt + 1 : cnt;
  }
  return cnt;
};

const solution = (T, nList) => {
  console.log(nList.map((n) => dfs(n)).join('\n'));
};

solution(L, datas);