백준 2921번 도미노 C++

리뷰

처음엔 문제가 이해가 안됐고, 이해가 된 후에는 점화식을 어떻게 세워야 할지 고민이 됐다. 정답률이 어떻게 80%가 넘는거지?

 

문제 풀이

1. 경우의 수를 생각하면 도미노 한칸은 i, 다른 도미노 한칸은 j라고 생각해 보자
2. i도미노가 0 ~ n까지 들어올때 j도미노는 i부터 n까지 들어올 수 있다.
3. 예를 들어 n이 3이라면 i도미노가 0일때 j도미노는 0~3까지 들어올 수 있다.
4. i도미노가 1일때 j도미노는 1~3까지 들어올 수 있다. 이를 n까지 반복한다.
5. for문이 종료되면 최종 정답을 출력해 준다.

 

참고 사항

n
1	x	0	1	1
	y	0	0	1
2	x	0	1	2	1	2	2
	y	0	0	0	1	1	2
3	x	0	1	2	3	1	2	3	2	3	3
	y	0	0	0	0	1	1	1	2	2	3
4	x	0	1	2	3	4	1	2	3	4	2	3	4	3	4	4
	y	0	0	0	0	0	1	1	1	1	2	2	2	3	3	4

x와 y가 각 도미노 칸이라고 생각하면 된다. 중복은 허용되지 않는다.

 

정답 코드

#include <iostream>

using namespace std;

int main() {
	int n, i, j, ans = 0;
	cin >> n;
	for (i = 0; i <= n; i++) {
		for (j = i; j <= n; j++) {
			ans += i;
			ans += j;
		}
	}
	cout << ans;
}