백준 1010 다리 놓기

 

 

https://www.acmicpc.net/problem/1010

1010번: 다리 놓기

#include <iostream>	
using namespace std;
int main()
{
	int x, y;
	int b[30];
	int t = 0;
	int count = 0;
	cin >> t;
	
	for (int st = 0; st < t; st++)
	{
		
		cin >> x >> y;

		if (x==y)
		{
			cout << 1<<"\n";
		}
		else
		{
			for (int i = 0; i < 30; i++) //배열을 1로 초기화
			{
				b[i] = 1;
			}

			for (int n = 0; n < x; n++)
			{
				for (int i = 0; i < y - x + 1; i++)
				{
					count = 0; //마지막 끝날때의 경우의 수만 더하면 됨으로 0으로 초기화
					if (i > 0) //첫번째는 무조건 1임으로 0보다 클 때만 더함
					{
						b[i] += b[i - 1];
						count += b[i];
					}
				}
			}

			cout << count<<"\n";
		}

	}
}

문제의 풀이 입니다.

조합론으로 풀면 간단하지만 저는 다른 방식으로 접근했습니다.

 

입력받은 다리의 N,M의 수가 같으면 경우의 수가 1개임으로 1출력

 

방식은 만약 N,M이 같지 않을때

1,M-N+1 → 2,M-N+2 → 3,M-N+3 → .... → N-1,M-1 → N,M로 증가하며 경우의 수를 구한다.

예를 들어 1,5이면 1,1,1,1,1 → 5가지

2,6이면 1,2,3,4,5 → 15가지

3,7이면 1,3,6,10,15 → 35가지

{
	b[i] += b[i - 1];
	count += b[i];
}

의 방식으로 늘어남 

 

결국 마지막의 

N,M일때의 

count가 답이된다.