[BOJ] 적록색맹

문제

적록색약 (https://www.acmicpc.net/problem/10026)

풀이

1. 초기접근

• 문제 조건 해석
  • n <= 100 이므로, 전형적인 dfs 문제다.
• 코드

#include <string>
#include <vector>

using namespace std;

long long d[101][100001];

int solution(int n, vector<int> money) {
  int answer = 0;

  d[0][0] = 1;
  for (int i=money[0] ; i<=n ; i+=money[0])
    d[0][i] = 1;

  for (int j=1 ; j<money.size() ; j++)
    for (int i=0 ; i<=n ; i++)
      if (i >= money[j])
        d[j][i] += d[j][i-money[j]] % 1000000007;

  answer = d[money.size()-1][n];
  return answer;
}

2. 파이썬 재귀 최대 깊이 제한

• 위와 같이만 하면, 런타임 오류가 뜬다.
• 이유를 찾아보고 하니, 파이썬에서 일반적으로 재귀 최대 깊이 제한이 있다고 한다. (1000정도라고 한다.)
• 따라서 재귀를 쓰는 경우 다음코드를 추가하라고 한다.

import sys
sys.setrecursionlimit(100000)

• 수정한 코드

import sys
sys.setrecursionlimit(100000)

#include <string>
#include <vector>

using namespace std;

long long d[111111];

int solution(int n, vector<int> money) {
  int answer = 0;

  d[0] = 1;
  for (int i=money[0] ; i<=n ; i+=money[0])
    d[i] = 1;

  for (int j=1 ; j<money.size() ; j++)
    for (int i=0 ; i<=n ; i++)
      if (i >= money[j])
        d[i] += d[i-money[j]] % 1000000007;

  answer = d[n];
  return answer;
}