본문 바로가기
반응형

DP4

백준 11727번 (2xn 타일링 2) c++ https://www.acmicpc.net/problem/11727 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net 문제풀이 이전에 풀이했던 2xn 타일링을 보고 오면 훨씬 쉽게 이해할 수 있다. 이 문제는 DP를 이용하여 푸는 문제이다. 다른 많은 풀이 사이트에서는 단순히 DP[i] = DP[i-1] + (DP[i-2]*2) 라는 이유를 N에 따라 세어보았을 때 이게 말이 된다라는 식으로 많이 적어놓았다. 하지만 밑에 적어 놓은 것을 보면 제대로 된 규칙을 알 수 있다. DP[i-2] 에는 1x2인 2개의 타일과 2x2인 1개의 타일이 붙.. 2023. 6. 28.
백준 11726번 (2xn 타일링) c++ https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 문제 풀이 이 문제는 DP를 이용하여 푸는 문제이다. 다른 많은 풀이 사이트에서는 단순히 DP[i] = DP[i-1] + DP[i-2] 라는 이유를 N에 따라 세어보았을 때 이게 말이 된다라는 식으로 많이 적어놓았다. 하지만 밑에 적어 놓은 것을 보면 제대로 된 규칙을 알 수 있다. DP[i-2] 에는 1x2인 2개의 타일이 붙고, DP[i-1] 에는 2x1인 1개의 타일이 붙은 두가지 경우의 수를 합치면 DP[i]가.. 2023. 6. 28.
백준 9655번 (돌 게임) c++ 문제 문제 풀이 문제의 조건을 제대로 파악해야 한다. 1. 둘 다 각각의 차례에 1개 또는 3개를 가져갈 수 있다. 2. 두 사람이 완벽하게 게임을 플레이 한다. 3. 게임은 상근이가 먼저 시작한다. N = 1 N = 2 N = 3 N = 4 N = 5 N = 6 SK CY SK CY SK CY 이렇게 각 N에 따라 답은 정해져 있다. 규칙을 보자면 짝수일 때, 홀수일 때 각각 답이 같은 것을 알 수 있다. 그래서 단순히 홀수, 짝수를 판별해 답을 도출할 수 있다. 전체 코드 #include using namespace std; int main(){ ios_base::sync_with_stdio(false); cin.tie(0); int N; cin >> N; if(N & 1){ cout N; bool .. 2022. 12. 27.
백준 1010번 (다리놓기) c++ 문제 문제풀이 이 문제는 두가지 방식으로 풀 수 있다. 1. 조합 2. DP 1. 조합 nCr 서로 다른 n개 중 r개를 뽑는 경우의 수를 조합 예를 들어 A, B, C, D, E 5명의 후보가 존재할 경우, 2명의 대표를 뽑는 경우의 수는? (A, B), (A, C), (A, D), (A, E) (B, C), (B, D), (B, E) (C, D), (C, E) (D, E) 답은 10이 된다. 현재 문제에 적용을 시켜보면 n = C, r = N가 된다. 코드 #include using namespace std; unsigned long long dp[101]; unsigned long long fact(int n){ if(dp[n]){ return dp[n]; } else{ dp[n] = n * fac.. 2022. 12. 24.
반응형

티스토리툴바