프로그래민👨‍💻

DP를 사용하는 전형적인 문제이다. 1X2, 2X2, 2X1 세가지 블럭이 있으므로 다음과 같은 점화식을 구할 수 있다. dp[N]= (dp[N-1]에서 세로블럭 1개 더해서 만들기) + (dp[N-2]에서 가로블록 2개 더해서 만들기) + (dp[N-2]에서 정사각형 블록 1개 더해서 만들기) 위와 같은 점화식으로 쉽게 dp를 구할 수 있고, 조건에서 10007로 나눈 수를 구하라 했으므로 연산 결과마다 10007을 나누어 주었다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 package boj.base; import java.io.BufferedReader; import java.io.InputStream..

DP로 푸는 문제이다.n 처음에 문제를 보았을 때, 재귀를 이용하여 접근하였다. 하지만 재귀를 시간초과가 발생하였다. 그래서 DP를 이용하여 풀어보았다. bottom-up 방식을 이용하여 1부터 N까지 갈수있도록 하였다. 이 과정은 시간복잡도가 n이므로 금방 구할수 있었다. 즉, dp[n]= min(dp[n/3], dp[n/2], dp[n-1]) +1 이라는 점화식을 이용하여 풀었다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 package boj.base; import java.io.BufferedReader; import java.io.InputStreamR..

이 문제는 DP로 해결하였다. 맨 처음 문제를 봤을때 재귀적인 그래프의 탐색형태로 접근하려고 했다. 하지만 N의 크기가 재귀를 사용하기에 너무 큰 경우의 수를 가지기에 재귀말고 DP로 접근하게 되었다. 일단 모든 맵의 칸에서 3가지의 경우의수를 가지고 했다. 파이프가 각각 가로,세로,대각선으로 깔리게 되는 3가지로 두었다. 그리고 만일 i,j에서 가로로깔리게 되는 경우의 수를 생각해보면 i-1,j 에서의 가로와 대각선의 경우의 수를 가질수 있게 된다. 이러한 방식으로 다음과 같이 생각하게 되었다. 1) i,j에서 가로의 파이프를 가지는 경우 : (i-1,j에서 가로) + (i-1,j에서 대각선) 2) i,j에서 세로의 파이프를 가지는 경우 : (i,j-1에서 세로) + (i,j-1에서 대각선) 3) i,..

간단해 보이는 문제지만 동적프로그래밍을 사용해야하는 문제이다. N=1000 이고 M=100000이므로 최악의 경우에는 for문을 사용하였을때 1억을 넘어가므로 일반적인 방식으로는 풀이를 할 수 없다. 그래서 arr에 저장할때 행별로 더해주며 누적값을 저장하였다. 그 후 행별로 누적된 값을 이용하여 연산을 하는 방식으로 문제를 해결해주었다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 package boj2; import java.io.BufferedReader; import java.io.InputS..