sm 기술 블로그

문제요약 입력된 값을 자릿수로 하여 이진수에서 00 이 붙어 있거나 아예 없는 모든 경우의 수에 15746을 나눈 나머지를 구하라. 설명 먼저 이 문제를 이해하고 규칙을 찾는건 크게 어렵지 않다. 다음과 같이 피보나치수열을 이루고 있음을 알고 있다. 피보나치 하면 먼저 재귀함수가 떠 오를 것이다. 하지만 재귀함수를 이용하면, 다음과 같이 메모리 초과 혹은 런타임 에러가 발생한다. RecursionError는 재귀를 너무 많이 하게 되면 발생하는 에러이다. 따라서 이 문제는 재귀함수로 푸는것은 불가능하다. 그러면 반복문을 사용해야한다. import java.util.*; import java.io.*; class Main { public static void main(String[] args) { Scan..

문제요약 입력된 값을 자릿수로 하여 이진수에서 00 이 붙어 있거나 아예 없는 모든 경우의 수에 15746을 나눈 나머지를 구하라. 설명 먼저 이 문제를 이해하고 규칙을 찾는건 크게 어렵지 않다. 다음과 같이 피보나치수열을 이루고 있음을 알고 있다. 피보나치 하면 먼저 재귀함수가 떠 오를 것이다. 동적프로그래밍 파트에다가 숫자가 매우 크므로 동적을 적용해 보았다. N = int(input()) memo = [0]*500 def Tile(N): if N == 1 or N == 2: memo[N] = N return memo[N] memo[N] = Tile(N-1)+Tile(N-2) return memo[N] print(Tile(N)%15746) 결과는 실패였다. 다음과 같이 메모리 초과 혹은 런타임 에러가..

import java.util.*; import java.io.*; class Main { static int[][][] memo; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringBuilder sb = new StringBuilder(); memo = new int[21][21][21]; while (true) { String[] inputs = br.readLine().split(" "); int a = Integer.parseInt(inputs[0]); int b = Integer.parseInt(i..

TOP - DOWN 방식 result = "" memo = [[[0 for _ in range(21)] for _ in range(21)] for _ in range(21)] def w(a,b,c): if a 20: return w(20,20,20) if memo[a][b][c] > 0 : return memo[a][b][c] if a < b < c : memo[a][b][c] = w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c) return memo[a][b][c] memo[a][b][c] = w(a-1, b, c) + w(a-1, b-1, c) + w(a-1, b, c-1) - w(a-1, b-1, c-1) return memo[a][b][c] while True: a,..