[SCPC 2021] 친구들

문제설명

• 입력으로 n 이 주어진다. 그 후 D1 ~ Dn 까지 입력으로 주어진다.
• i 번 사람이 i+Di 번과 친구이고, 친구관계가 i 가 j를 친구라 생각한다면, j도 i를 친구라 생각 할 때, 친구 관계인 극대 그룹의 개수를 출력하는 문제입니다.
• 극대 그룹이란 "현재 이 그룹 안에서 뽑은 임의의 2명이 서로 친구이면서", "이 성질을 깨지 않고 이 그룹에 누군가를 추가할 수 없음" 을 말합니다.

정확한 문제 본문은 대회종료 후 https://www.codeground.org/ 에서 확인할 수 있을것이다.

 

풀이 

일단, 난 알고리즘을 잘 모른다. 일단 주어진 예제 입력으로부터 규칙을 찾아봤다. 

8

10

5

4

2

5

1

3

1

9

이 입력으로부터 문제 조건에 의해 총 10개의 친구관계를 알 수 있다. 입력 순서대로 친구관계를 서술하면,

1	2	3	4	5	6	7	8	9	10
9		8	8	7		8		10

그리고, 이를 친구의 친구도 친구다 라는 조건을 이용해 그룹으로 묶으면, (1, 9 , 10) , (2), (3, 4, 5, 7, 8), (6) 이렇게 4개의 그룹으로 묶인다. 따라서 이 경우 답은 4이다. 이 외에도 몇가지 입력에 대한 결과를 도출해보면, 한가지 공식이 나온다.

n - (두번째 표에서 각 숫자가 중복으로 나타나는경우, 그 중복의 수 -1 ) 이 답이된다. 다시 말하면, 위 두번째 표의 경우, 첫번째 행은 1 ~ n 이 한번씩 등장하므로, 두번째 행에서 등장한 숫자의 갯수를 빼면 된다. 왜냐하면, 최대 극대 그룹의 수는, n 개인데, 이중 어떤 두 수가 친구관계라면, 같은 극대그룹에 속할 것이고, 따라서 최대치에서 같은 그룹으로 합쳐지는 것들의 수를 빼면, 극대그룹의 수가 나오게 된다. 이는, n개의 입력에 대해 친구를 구하고, 이를 다시 탐색하는 것이므로, O(n) 안에 문제가 풀리게 된다.

 

코드

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Solution {
	static int Answer;

	public static void main(String args[]) throws Exception	{
		Scanner sc = new Scanner(System.in);

		int T = sc.nextInt();
		for(int test_case = 0; test_case < T; test_case++) {
			int n = sc.nextInt();
			int array[] = new int[n];
			for(int i=0;i<n;i++) {
				array[i] = sc.nextInt();
			}
			List<Friend> list = new ArrayList<Friend>();
			int counts[] = new int[n];
			for(int i=0;i<n;i++) {
				Friend friend = new Friend();
				friend.first = i;
				if(i+array[i]>=n)
					friend.second = -1;
				else
					friend.second = i+ array[i];
				counts[friend.first]++;
				if(friend.second!=-1) {
					counts[friend.second]++;
				}
				list.add(friend);
			}
			Answer = n;
			for(int i=0;i<n;i++) {
				if(counts[i]>1) 
				Answer = Answer-(counts[i]-1);
			}
			System.out.println("Case #"+(test_case+1));
			System.out.println(Answer);
		}
	}
}
class Friend {
	int first;
	int second;
}

이는 대회 당시 내가 제출했던 코드다. 지금 다시 보니까 대체 왜 이걸 이따구로 작성했는지 이해가 안간다.아마, 대회라는 압박때문에 머리가 잘 안돌아갔나보다. (아니면, 그사이에 내가 성장한건가..?)

알고리즘을 다시 그대로 문제로 옮기면 아래와같다.

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Solution {
	static int Answer;

	public static void main(String args[]) throws Exception	{
		Scanner sc = new Scanner(System.in);

		int T = sc.nextInt();
		for(int test_case = 0; test_case < T; test_case++) {
			int n = sc.nextInt();
			int D[] = new int[n+1];
			for(int i=1;i<=n;i++) {
				D[i] = sc.nextInt();
			}
			int friends[] = new int[n+1];
			Answer = n;
			for(int i=1;i<=n;i++) {
				if(i+D[i] <=n) {
					Answer--;
				}
			}
			System.out.println("Case #"+(test_case+1));
			System.out.println(Answer);
		}
	}
}