[BOJ 3182 // C++] 한동이는 공부가 하기 싫어!

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

 

이번에 볼 문제는 백준 3182번 문제인 한동이는 공부가 하기 싫어!이다.
문제는 아래 링크를 확인하자.

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

3182번: 한동이는 공부가 하기 싫어!

각 선배에 대하여 해당 선배부터 질문을 시작할 때 만나게 되는 선배의 수는 $N$ 이하임을 알 수 있다. 전체 선배의 수가 1000명이므로, 모든 각 선배에 대하여 질문을 시작해보더라도 선배에게 질문을 하는 횟수는 $N^2$ 이하임을 알 수 있다.

 

따라서 모든 선배에 대하여 그 선배부터 질문을 시작할 때 총 몇 명의 선배를 만나게 되는지를 구하는 시뮬레이션을 각각 돌려 문제를 해결하는 방법은 문제를 해결하기에 충분한 시간복잡도를 가진다. 이와 같은 방법으로 문제를 해결하자.

 

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

#include <iostream>
#include <cstring>
using namespace std;

int N;
int arr[1001];
int visited[1001];

int ans, mx;

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

	cin >> N;
	for (int i = 1; i <= N; i++) cin >> arr[i];

	for (int i = 1; i <= N; i++) {
		memset(visited, 0, sizeof(visited));
		int cnt = 0, idx = i;
		while (!visited[idx]) {
			visited[idx] = 1;
			idx = arr[idx];
			cnt++;
		}
		if (mx < cnt) mx = cnt, ans = i;
	}

	cout << ans;
}