나다김강니

11727 : 2xn 타일링 2문제2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.아래 그림은 2×17 직사각형을 채운 한가지 예이다.입력첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)  출력첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.  문제 풀이풀어버림.....사실 2xn 첫번째 문제 덕분에 푼 듯..?점화식 > dp[n-1] + dp[n-2] * 2dp[n-1]은 경우가 하나뿐임 그냥 세로타일 채우기dp[n-2]는 정사각형, 세로두개, 가로두개 이렇게 경우가 3개인데 세로 두개는 dp[n-1]에서 들어가니께 뺀다! 실행 코드import java.util.Scanner;public class P1..

9095 : 1, 2, 3 더하기문제정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.1+1+1+11+1+21+2+12+1+12+21+33+1정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오. 입력첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다. 출력각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다.입력출력34710744274 문제 풀이점화식+1을 하는 경우+2를 하는 경우+3을 하는 경우를 다 더함dp[j] = dp[j - 1] + dp[j - 2] + dp..

2579 : 계단 오르기문제계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다.예를 들어 와 같이 시작점에서부터 첫 번째, 두 번째, 네 번째, 여섯 번째 계단을 밟아 도착점에 도달하면 총 점수는 10 + 20 + 25 + 20 = 75점이 된다.계단 오르는 데는 다음과 같은 규칙이 있다.계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.마지막 도착 계단은 반드시 밟아야 한다.따라서 첫 번..

DP(Dynamic Programming)복잡한 문제를 간단한 여러 개의 문제로 분리하여 부분의 문제들을 해결해 최종적으로 복잡한 문제의 답을 구한다. 💡 동적 계획법(DP)의 핵심 이론1️⃣  동적 계획법의 원리와 구현 방식 큰 문제를 작은 문제로 나눌 수 있어야 한다.작은 문제들이 반복돼 나타나고 사용되며 이 작은 문제들의 결과값은 항상 같아야 한다.모든 작은 문제들은 한 번만 계산해 DP테이블에 저장하며 추후 재사용할 때는 이 DP 테이블을 이용한다.-> 메모이제이션 기법동적 계획법은 톱-다운 방식(top-down)과 바텀-업(bottom-up) 방식으로 구현할 수 있다. 2️⃣  피보나치 수열(동적 계획법의 가장 대표적인 문제)피보나치 수열 공식D[N] = D[N-1] + D[N-2] 동적 계..