기록하기록

내가 푼 풀이가 틀렸다고 나왔길래 정답을 찾아서 비교해보는 과정을 거쳤다. 괄호를 붙이지 않아 우선순위 적용이 잘못 되었었다. - 수정 전 dp2[0][i] = dp2[0][i-1]+dp2[1][i-1]+dp2[2][i-1] % 9901; dp2[1][i] = dp2[0][i-1]+dp2[2][i-1] % 9901; dp2[2][i] = dp2[0][i-1]+dp2[1][i-1] % 9901; - 수정 후 dp2[0][i] = (dp2[0][i-1]+dp2[1][i-1]+dp2[2][i-1]) % 9901; dp2[1][i] = (dp2[0][i-1]+dp2[2][i-1]) % 9901; dp2[2][i] = (dp2[0][i-1]+dp2[1][i-1]) % 9901; - 풀이 코드 import java..

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; public class Main { static int [][] dp = new int[15][15]; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int tc = Integer.parseInt(br.readLine()); for (int i = 0; i < tc; i++) { int n = Integer.pars..

import java.util.*; public class Main { static int [][] dp = new int[100][100]; public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int m = sc.nextInt(); System.out.println(solution(n, m)); } private static int solution(int n, int m) { if(dp[n][m]>0) return dp[n][m]; else if(n==m || m == 0) return 1; else return dp[n][m] = solution(n-1,m-1) + solut..

https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net def solution(n): dp = [0] * (n + 1) for i in range(n+1): dp[i] = i if i

https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 탑다운, 바텀업 두가지 방식으로 풀긴 했는데, 탑다운 방식으로 하니까 시간초과가 났다. max_num = 10**20 def solution(n,count): global max_num if n == 1: max_num = min(max_num,count) if n % 3 == 0: solution(n//3,count+1) if n % 2 == 0: solution(n // 2, count +1) if n > 1: solution(n-1,count+1) return max_num def solution2(n):..

동적 계획법이라는 것에 대해 공부해보는 시간을 가졌습니다. '완전탐색 < DP' 라고 합니다. 문제를 쪼개고, 작은 단위의 답을 구하고, 그걸 바탕으로 더 큰 문제의 답을 구하는 과정을 반복하는 방법입니다. 오늘은 맛보기로 DP의 대표작인 피보나치 수열에 대해 간단하게 알아보았습니다. # recursive def f(n): if n < 2: return n return f(n-1) + f(n-2) # top - down cache = [-1] * 37 def f2(n): if cache[n] != -1: return cache[n] cache[n] = n if n < 2 else f2(n-1) + f2(n-2) return cache[n] # bottom - up fibo = [-1] * 37 def f..