문제

[백준] 다리놓기

접근

기본적인 1:n의 경우의 수가 계속 반복되는 형태

[1][n] 일 때 :

경우의 수는 n과 같다

[2][n] 일 때 :

[1][n-1] + [1][n-2] + ... + [1][1]일 때와 같다

시작이 n-1로 시작하는 이유는 1개짜리 다리 [1][n]을 위해서 '1'을 썼기 때문에 사용할 수 있는 남은 다리가 n-1부터 시작하기 때문

[3][n] 일 때

  [3][5]
->
  [2][4] + [2][3] + [2][2] + [2][1]
->
  ([1][3]+[1][2]+[1][1])
+ ([1][2]+[1][1])
+ ([1][1])
+ (0))  

풀이

#include <iostream>
using namespace std;

int dp[31][31];


int main() {
	int t;
	cin >> t;

	for (int i = 1; i <= 30; i++)
	{
		dp[1][i] = i;				// 1 대 i는 경우의 수가 i와 같다 
	}

	for (int i = 2; i <= 30; i++){	// 2대 다 일 때부터 모든 경우의 수 미리 계산
		for (int j = i; j <= 30; j++){
			for (int k = j-1; k >= 1; k--)
			{
				dp[i][j] += dp[i - 1][k];
			}
		}
	}

	while (t--) {
		int n, m; cin >> n >> m;
		cout << dp[n][m] << '\n';
	}

	return 0;
}



// https://ip99202.github.io/posts/%EB%B0%B1%EC%A4%80-1010-%EB%8B%A4%EB%A6%AC-%EB%86%93%EA%B8%B0/

참고블로그
감사합니다

개념정리

개념
반복에 따른 감소의 엄밀	점화식을 세우고 구현하는 것이 어려움 / for 문에 사용되는 변수를 조절하는 연습 필요

생각한 점

아이디어는 떠오르는 데 구현에서 어려움을 겪는다
사실 이건 아이디어가 정밀하지 않아서인가?

생각한 논리를 for문 혹은 재귀문으로 표현하는 것이 어렵다

재귀과 for문을 많이 연습해야겠다

종류	중요
재귀	매개변수를 다루는 방법
for문	int 범위를 변칙적으로 다루는 것이 정말 중요해보인다