백준/동적프로그래밍15 백준 1562 c++ "계단 수" -PlusUltraCode- https://www.acmicpc.net/problem/1562 [필자 사고] 어려운 문제다.처음에 DNS를 이용하여 풀려고 했지만 경우의 수를 생각해보니 시간초과가 나온다.어쩔 수 없이 30분 고민하고 풀이 힌트를 보았더니 비트마스킹을 이용한 동적프로그래밍 문제다. 나는 처음으로 비트마스킹 알고리즘을 만나게 되었따. 간단히 말하자면1000000000 이라는 2진수로 이루어진 bit가 있고1위의 기존 bit | new bit 를 하게 되면1000010000 식으로 게임 처럼 1로 바껴서 on모드가 된다.이러한 방식으로 아래의 문제를 해결했다. 소스코드 해설은 아래와 같다 1.코드 개요이 코드는 숫자의 길이 N이 주어졌을 때, 계단 수를 계산하는 프로그램입니다. 계단 수는 숫자의 각 자릿수가 1씩 증.. 2024. 12. 26. 백준 c++ 1904 "01타일" -PlusUltraCode- https://www.acmicpc.net/problem/1904 [필자 사고] 문제를 보고 일단 N=4까지 구해보았다. N=1 일때 타일 종류 1 총 1개 2일때 타일 종류 00 11 총 2개 3일때 타일 종류 001, 100, 111 총 3개 4일때 타일종류 0000 ,0011 1100 1111 1001 총 5개 5일때는 00001, 00100, 00111 10000, 10011, 11001, 11100, 11111 총 8개이다. 규칙성을 찾아보면 피보나치 수열이라는 점을 알 수 있다. 동적프로그래밍 문제를 풀 때는 어느정도의 특수한 상황을 항상 생각하면서 풀어야 될 거같다. [소스 코드]#include #include using n.. 2024. 5. 10. 백준 12865 c++ "평범한 배낭" -PlusUltraCode- https://www.acmicpc.net/problem/12865 [필자 사고]Dp문제이다.Dp문제에서 핵심은 Dp를 어떻게 정의하느냐에 있다고 생각한다. 필자는 Dp[i][k] 라고 선언했고 k는 무게를 의미하며 i는 가방의 종류를 의미한다. Dp값은 최대 가치를 의미한다. max(DP[i - 1][j], DP[i - 1][j - W[i]] + V[i])이 코드가 핵심이라고 생각한다. 현재의 가방의 최대치를 구하기 위해 먼저 해당 가방의 무게가 k를 넘지 않아야 된다. 다음으로 생각할 것은 현재 가방에 넣은 물건들의 가치 최대치이다. 1. 만약 해당 가방의 무게가 k보다 작은경우에서 이전 Dp[i-1][j] 의 가치가 높은지 아니면 Dp[i-1][j-W[i]]+V[i] 높은지 .. 2024. 5. 9. 백준 c++2749 "피보나치 수 3" -PlusUltraCode- https://www.acmicpc.net/problem/2749 [필자사고]https://www.acmicpc.net/problem/9471 이 문제는 피사노 주기를 알면 쉽게 풀 수 있는 문제이다. 피사노 주기의 특징은 k(10n) = 15×10(n-1) 와 같은 특징이 있따. 예를들어 1000000으로 나눠야 되는 상황이 있으면 k(10^6) = 15x10(10^5) 의 공식이 성립하여 k의 값은 1500000가 된다. 즉 100만으로 나누게 될 경우 15만마다 주기가 생긴다는 점이다. 이 문제의 N의 값은 매우 크기 때문에 모든 값을 다 담게 되면 메모리 초과가 생길것이다. 여기서 핵심은 15만 마다 주기가 반복되므로 15만의 크기의 배열만 확인하면 문제를 쉽게 해결할 수 있따. [소.. 2024. 5. 8. 이전 1 2 3 4 다음
