취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 13021번 문제인 공 색칠하기이다.
문제는 아래 링크를 확인하자.

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

어떤 색칠의 결과가 최종 결과에 영향을 준다면 해당 색칠을 어떤 색으로 하였는지에 따라 구하는 경우의 수의 값이 2배가 됨을 관찰하자.

색칠을 역순으로 살펴나가면서 이후로 위에 색이 덧칠되지 않을 칸이 해당 색칠에 존재하는지를 살피면 각 색칠의 결과가 최종 결과에 영향을 주는지를 알 수 있다.

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;

int N, M;
ll ans = 1;
bool visited[1001];
vector<pair<int, int>> vec;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N >> M;
	while (M--) {
		int L, R; cin >> L >> R;
		vec.emplace_back(make_pair(L, R));
	}
	while (!vec.empty()) {
		int L = vec.back().first, R = vec.back().second; vec.pop_back();
		bool chk = 0;
		for (int i = L; i <= R; i++) {
			if (visited[i]) continue;
			visited[i] = 1, chk = 1;
		}
		if (chk) ans *= 2;
	}
	cout << ans;
}