오늘은 어제와 같은 DP 관련 문제를 풀어보았다.
주어진 정수의 길이만큼의 이진수의 경우의 수를 출력하는 문제인데,
0은 00으로 붙여서 사용해야 했다.
그래서 1인 경우부터 직접 구해서 규칙을 찾아냈다.
public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.parseInt(br.readLine()); System.out.println(dp(N)); } public static int dp(int N){ int[] dp = new int[N + 1]; dp[1] = 1; dp[2] = 2; for(int i=3; i<=N; i++){ dp[i] = 2*(dp[i-1]-1) + 1; } return dp[N]; }
N이 5인 경우까지 나열해보니 위와 같이 풀으면 될 것 같아서 코딩하고 제출했더니 틀렸다고 나오는 것이었다,,🤔
무엇이 잘못됐는지 다시 나열해보고, 검색도 해보니 N=5인 경우 00000까지 포함시켜서 규칙을 잘못 체크하고 있었었다,,,ㅎ
아주 간단한 피보나치 수열이었는데,,,ㅎ,,,,,,,,😅
그래서 다시 푼 풀이는 아래와 같았다.
public static int dp(int N){ int[] dp = new int[N+1]; dp[1] = 1; dp[2] = 2; for(int i=3; i<=N; i++){ dp[i] = (dp[i-1] + dp[i-2]) % 15746; } return dp[N]; }
피보나치 수열인데 문제에서 15746으로 나눈 나머지 값을 출력하라고 표시되어 있어서 %15746 까지 추가해서 제출을 했는데,
왜,,,어째서,,,,,?
검색해서 다른 분들의 풀이를 봐도 내 풀이가 맞는 것 같은데,,,,왜,,,,?😞
왜 런타임 에러인지는 다음에 알아보도록 하자,,
