알고리즘/문제풀이 - 백준

백준 1904 01타일

문제 : https://www.acmicpc.net/problem/1904 풀이 n=1 1 n=2 00 11 n=3 100 111 001 n=4 0000 0011 1100 1111 1001 n=5 00100 00111 00001 10000 10011 11100 11111 11001 개수 : 1 개수 : 2 개수 : 3 개수 : 5 개수 : 8 n이 3일때는 n이 1일때의 1에 00을 앞에 붙인 001, n이 2일때의 00, 11에 앞에 1을 붙인 100, 111 총 3개가 올 수 있다. 앞에 01, 10, 0은 못붙인다. 이를 확장하면 n = n-1 + n-2의 점화식이 나온다. dp의 bottom-up으로 구현한다. 구현 %15746을 해주지 않으면 약 n이 90에서 long long 자료형을 초과한다..

2019. 7. 8. 14:04
알고리즘/문제풀이 - 백준

백준 1003 피보나치 함수

문제 : https://www.acmicpc.net/problem/1003 서론 DP문제이며 메모이제이션을 이용하여 풀이했다. 아이디어 n 0 1 2 3 4 5 6 7 8 피보나치 0 1 1 2 3 5 8 13 21 0의 개수 1 0 1 1 2 3 5 8 13 1의 개수 0 1 1 2 3 5 8 13 21 위 표를 보면 규칙성이 있는데, 피보나치 수열과 1의 개수 수열은 같다. n이 0일때를 제외하고, 피보나치 수열의 n은 0의 개수 수열의 n+1과 같다. 따라서 0의 개수는 n번째 피보나치수를, 1의 개수는 n-1번째 피보나치 수를 출력하면 된다. 메모이제이션 함수에서 fib(n) = fib(n-1) + fib(n-2)를 계산할때 이미 fib(n-1)과 fib(n-2)를 이전에 계산한적이 있어서 배열에..

2019. 6. 28. 21:35