실력키우기 숫자고르기(C++)

1459 : 숫자고르기

제한시간: 1000 ms    메모리제한: 64 MB
해결횟수: 455 회    시도횟수: 1341 회   

세로 두 줄, 가로로 N개의 칸으로 이루어진 표가 있다. 첫째 줄의 각 칸에는 정수 1, 2, …, N이 차례대로 들어 있고 둘째 줄의 각 칸에는 1이상 N이하인 정수가 들어 있다. 첫째 줄에서 숫자를 적절히 뽑으면, 그 뽑힌 정수들이 이루는 집합과, 뽑힌 정수들의 바로 밑의 둘째 줄에 들어있는 정수들이 이루는 집합이 일치한다. 이러한 조건을 만족시키도록 정수들을 뽑되, 최대로 많이 뽑는 방법을 찾는 프로그램을 작성하시오. 예를 들어, N=7인 경우 아래와 같이 표가 주어졌다고 하자.

 

이 경우에는 첫째 줄에서 1, 3, 5를 뽑는 것이 답이다. 첫째 줄의 1, 3, 5밑에는 각각 3, 1, 5가 있으며 두 집합은 일치한다. 이 때 집합의 크기는 3이다. 만약 첫째 줄에서 1과 3을 뽑으면, 이들 바로 밑에는 정수 3과 1이 있으므로 두 집합이 일치한다. 그러나, 이 경우에 뽑힌 정수의 개수는 최대가 아니므로 답이 될수 없다.

 

입력의 첫째 줄에는 N(1≤N≤100)을 나타내는 정수 하나가 주어진다.

그 다음 줄부터는 표의 둘째 줄에 들어가는 정수들이 순서대로 한 줄에 하나씩 입력된다.

첫째 줄에 뽑힌 정수들의 개수를 출력하고 그 다음 줄부터는 뽑힌 정수들을 작은 수부터 큰 수의 순서로 한 줄에 하나씩 출력한다.

[Copy] 7 3 1 1 5 5 4 6

[Copy] 3 1 3 5

출처 : KOI 전국 1996 초2

/**************************************************************
    Problem: 1459
    User: a132034
    Language: C++
    Result: Success
    Time:0 ms
    Memory:1092 kb
****************************************************************/
 
 
#include    <cstdio>
#pragma warning(disable:4996)
 
int A[111];
int RES[111];
int N;
bool search(int index)
{
    int first = index; //초기값
    int second = A[index];
    for (int i = 0; i<N; ++i)
    {
        if (first == second)
            return true;
        second = A[second];
    }
    return false;
}
int main()
{
 
    scanf("%d", &N);
 
    for (int i = 1; i <= N; ++i)
        scanf("%d", &A[i]);
 
    for (int i = 1; i <= N; ++i)
    {
        if (search(i))
            RES[i] = RES[A[i]] = 1;
    }
 
    int sum = 0;
    for (int i = 1; i <= N; ++i)
    if (RES[i] == 1)
        sum++;
    printf("%d\n", sum);
    for (int i = 1; i <= N; ++i)
    if (RES[i] == 1)
        printf("%d\n", i);
 
    return 0;
}
 

재귀..? 로 풀 수 있는 문제 

사실 위의 코드도 맞긴 하나 약간 효율성은 떨어지는것 같다. 

일단 문제의 요지는 

1번부터 n번까지 점 마다 돌면서 자기 자신으로 돌아오는 순환이 생기는지 확인하여 순환이 생기는 숫자를 선택하였다. 

위    : 1 2 3 4 5 6 7

아래 : 3 1 1 5 5 4 6

일 경우 

위를 기준으로 

1 >>> 1은 3을 보고 -> 3은 다시 1을 본다. 시작과 끝이 동일하므로 순환. 1, 3은 선택할 수 있다. 

2 >>> 2는 1을 보고 1은 3을 보고 3은 1을 본다. 1-3-1-3이 계속 바뀌므로 2가 될 수 없으니 선택하지 않는다. 

3 >>> 3은 1을 보고 1은 3을 본다. 3 - 1 - 3으로 순환하므로 선택(1 선택할 때 1,3을 이미 선택함)

4 >>> 4는 5를 보고 5는 5를 본다. 5 - 5 - 5 - 5로 4가 올 수 없다. 선택하지 않는다.

5 >>> 5는 5를 본다. 순환하므로 선택. (여기까지 1, 3, 5를 선택)

6 >>> 6은 4를 보고 4는 5를 보고 5는 5를 본다. 계속 5만 나오므로 6이 나올 수 없다. 선택하지 않는다.

7 >>> 7은 6을 보고 6부터는 위와 동일... 7 - 6 - 4 - 5 - 5 - 5... 선택하지 않는다. 

선택한 수는 1, 3, 5가 된다. 

다시 짜면 코드를 더 효율적으로 짤 수 있을 것 같다...