백준 7140 (C++) 데이터 만들기 1

최초 업로드: 2025-10-28 05:05:14

최근 수정 시간: 2025-10-28 05:05:14

게시자: rlatjwls3333

카테고리: 백준

# [Gold IV] 데이터 만들기 1

[문제 링크](https://www.acmicpc.net/problem/7140)

## 문제 설명

오늘날 세상에는 많은 프로그래밍 대회가 있다. 대회에 사용할 좋은 프로그래밍 문제를 만드는 일은 매우 어렵다. 그 중 가장 어려운 일은 테스트 데이터를 만드는 일이다. 좋은 테스트 데이터는 문제의 의도에 맞게 짠 코드와 그렇지 않은 코드를 구별해 낼 수 있어야 한다. 또, 대부분의 경우에 올바른 결과를 내지만, 특별한 케이스에서는 틀리는 소스를 찾아낼 수도 있어야 한다.

이 문제는 지금까지 풀어왔던 문제와는 다르게 문제를 푸는 소스를 제출하는 문제가 아니다. 바로 테스트 케이스를 만드는 문제이다.

지금 상근이는 그래프 문제의 데이터 하나를 만들어야 한다. 이때, 상근이가 만들 데이터 X는 코드 A와 코드 B에 대해서 다음 조건을 만족해야 한다.

또, 데이터는 작을 수록 좋기 때문에, 최대 T개의 정수로 이루어져 있어야 한다.

위의 조건을 만족하는 입력 데이터를 만드는 프로그램을 작성하시오.

## 입력

이 문제는 입력이 없다.

상근이가 데이터를 만들 문제는 <a href="https://www.acmicpc.net/problem/7612">7612번 SSSP</a>이고, 사용할 코드 A는 ModifiedDijkstra, B는 FloydWarshall이다. (소스는 아래 힌트에 있다)

코드를 보면 counter 변수가 있다. 이 변수 값이 1,000,000을 넘으면 TLE이다.

또, T는 107이다.

## 출력

입력 데이터를 출력하면 된다.

## 힌트
<ul>
	<li>ModifiedDijkstra
	<ul>
		<li><a href="https://www.acmicpc.net/data/source/ModifiedDijkstra.c">C</a></li>
		<li><a href="https://www.acmicpc.net/data/source/ModifiedDijkstra.cpp">C++</a></li>
	</ul>
	</li>
	<li>FloydWarshall
	<ul>
		<li><a href="https://www.acmicpc.net/data/source/FloydWarshall.c">C</a></li>
		<li><a href="https://www.acmicpc.net/data/source/FloydWarshall.cpp">C++</a></li>
	</ul>
	</li>
</ul>

## 풀이
N³인 플로이드-와샬 알고리즘을 터트리는 문제입니다. 간선은 연결하지 않고, 정점의 개수만 최대로 하면 됩니다.

``` c++
#include<bits/stdc++.h>
using namespace std;

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	cout << "103\n";
	for(int i=0;i<103;i++) cout << "0\n";
	cout << "1\n1 2";
}
```