CSES 3. Rectangle Cutting (1744)

출처: https://cses.fi/problemset/1744

---

문제 설명

Given an a×b rectangle, your task is to cut it into squares. On each move you can select a rectangle and cut it into two rectangles in such a way that all side lengths remain integers. What is the minimum possible number of moves?

입력 

The only input line has two integers a and b.

출력

Print one integer: the minimum number of moves.

입력 예

3 5

출력 예

3

제약조건

1 <= a, b <= 500

---

문제 풀이

모두 정사각형이 되도록 직사각형을 자를때 최소 횟수를 구하는 문제이다. 가로로 자르는 경우와 세로로 자르는 경우로 나눠서 각각 한번 자를때마다, 최소값들을 갱신한다.

프로그램 내용

...   
for(int i=1; i<=a; ++i) {
	for(int j=1; j<=b; ++j) {
		if(i^j)
			dp[i][j]= INT_MAX;
		for(int k=1; k<i; ++k) // 가로로 자르는 경우
			dp[i][j]=min(dp[i][j], dp[k][j]+dp[i-k][j]+1);
		for(int k=1; k<j; ++k) // 세로로 자르는 경우
			dp[i][j]=min(dp[i][j], dp[i][k]+dp[i][j-k]+1);
	}
}
...

 

Dynamic Programming ( link )