728x90 반응형 이것이 코딩테스트다2 [이것이 코딩테스트다] 다이나믹 프로그래밍(DP) 문제 - 바닥 공사 문제가로의 길이가 N, 세로의 길이가 2인 직사각형 형태의 얇은 바닥이 있다. 태일이는 이 얇은 바닥을 1x2의 덮개, 2x1의 덮개, 2x2의 덮개를 이용해 채우고자 한다. 이때 바닥을 채우는 모든 경우의 수를 구하는 프로그램을 작성하시오. 예를 들어 2x3 크기의 바닥을 채우는 경우의 수는 5가지이다. 입력 조건- 첫째 줄에 N이 주어진다. (1 출력 조건- 첫째 줄에 2xN 크기의 바닥을 채우는 방법의 수를 796,796으로 나눈 나머지를 출력한다. 입력 예시3 출력 예시5문제 풀이이 문제는 작은 문제를 활용해 큰 문제를 해결할 수 있는 전형적인 DP 문제이다. 마지막에 어떤 덮개를 추가하냐에 따라 점화식을 도출할 수 있다. - 마지막에 1x2 타일을 추가하는 경우: dp[n-1]개의 경우에.. 2025. 2. 19. [이것이 코딩테스트다] 다이나믹 프로그래밍(DP) 문제 - 개미 전사 문제개미 전사는 부족한 식량을 충당하고자 메뚜기 마을의 식량창고를 몰래 공격하려고 한다. 메뚜기 마을에는 여러 개의 식량창고가 있는데 식량창고는 일직선으로 이어져 있다. 각 식량창고에는 정해진 수의 식량을 저장하고 있으며 개미 전사는 식량창고를 선택적으로 약탈하여 식량을 빼앗을 예정이다. 이때 메뚜기 정찰병들은 일직선상에 존재하는 식량창고 중에서 서로 인접한 식량창고가 공격받으면 바로 알아챌 수 있다. 따라서 개미 전사가 정찰병에게 들키지 않고 식량창고를 약탈하기 위해서는 최소한 한 칸 이상 떨어진 식량창고를 약탈해야 한다. 예를 들어 식량창고 4개가 다음과 같이 존재한다고 가정하자. 이때 개미 전사는 두 번째 식량창고와 네 번째 식량창고를 선택했을 때 최댓값인 총 8개의 식량을 빼앗을 수 있다. 개미 .. 2025. 2. 19. 이전 1 다음 728x90 반응형
