취미로 코딩하기

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

이번에 볼 문제는 백준 7146번 문제인 데이터 만들기 7이다.
문제는 아래 링크를 확인하자.

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

백트래킹이 빠른 알고리즘은 아니기에 적절한 그래프를 대충 구성해주기만 해도 주어진 문제의 코드의 연산량을 크게 할 수 있다.

다만 여기서 주의해야 할 점은 연산량이 매우 많다는 것과 "counter 변수의 값이 1000000을 넘겼다"는 것이 동치가 아니라는 점이다. counter 변수는 부호있는 32비트 정수 자료형인 int로 선언되어있어 연산량이 매우 커질 경우 오버플로우가 일어나게 된다. 따라서 그냥 단순히 오래 걸리는 데이터를 만들 경우 약 절반의 확률로 counter 변수의 값이 음수가 되어 틀릴 수도 있다.

적당한 그래프를 구성해 주어진 코드의 counter 변수가 실제로 1000000이 넘는 값으로 실행을 마치는지 직접 확인한 다음 답으로 제출하자.

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

#include <iostream>
using namespace std;

int V = 999, E = 1501;
int a = 60, b = 61;

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

	cout << V << ' ' << E << '\n';
	for (int e = 0; e < E; e++) {
		if (b > 61) {
			b = a;
			a--;
		}
		cout << a << ' ' << b << '\n';
		b++;
	}
}

(BOJ Random Defense #6)