117262 [백준] JAVA 자바 : 2×n 타일링 2 (11726번) 직전 문제인 2×n 타일링에서 추가할 수 있는 블럭의 개수가 하나 늘어난 케이스이다. 이건 2×n 타일링 문제를 이해하고 푸셨다면… 진짜 2분 안에 해결하실 수 있을 것 같다. 기존의 dp[i] = dp[i-1] + dp[i-2]라는 코드는 dp[i]에 1×2로 채우는 경우 + 2×1로 채우는 경우를 뜻했다. 그러나 2×1로 채우는 경우의 수는 2×2로 채우는 경우의 수와 똑같으므로… dp[i-2]를 더해줄 때 2배를 해서 더해주면 된다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Tiling_2n_2 { public static int stoi(String .. 2024. 1. 22. [백준] JAVA 자바 : 2×n 타일링 (11726번) 사실 이 문제 이전에 나온 1로 만들기 문제는 못 풀어서 구글링해서 겨우 풀었는데…ㅋㅋ DP 알고리즘을 한 번 이해하고 나니까 이런 문제 정도는 굉장히 쉽게 풀리는 듯? 아직 실버3 수준이라서 그런지… 조금만 사고하면 어렵지 않게 풀 수 있다. DP알고리즘의 여느 때처럼 이전 값들을 저장할 수 있는 배열을 만들어준 다음 0번째 인덱스와 1번째 인덱스에 1을 할당한다. (초깃값 설정) 이후 Bottom-Top 방식을 채용해서 i를 2부터 X까지 반복시키면서 dp[i]에는 dp[i-1] + dp[i-2], 즉 1×2로 채우는 방식 + 2×1로 채우는 방식의 경우의 수를 더해주면 된다. import java.io.BufferedReader; import java.io.IOException; import jav.. 2024. 1. 22. 이전 1 다음 반응형
