[BJO][2309] 일곱 난쟁이

[브루트 포스 단계 - 01] 9개 중 7개의 합이 100이 되는 것을 구하는 문제

- 출처 : https://www.acmicpc.net/problem/2309

  ViusalStudio를 사용할 경우 계속해서 컴파일 오류를 뱉어낼 수 있다. VisualStudio와 다른 컴파일러인 GCC를 기반으로 한 자동 채점 시스템 때문으로 보인다. 백준 온라인을 처음 접하는 사용자라면 참고할 것. 백준 온라인 소개와 관련한 팁들은 여기를 클릭. 

  문제 텍스트만 읽어봤을 때 9개의 수 중 조건을 만족하는 수 한 쌍을 구해야 한다는 것이 바로 보일 것이다. 문제의 풀이 방향은 잡혔으니 풀이 방법을 고민해보자. 당장 떠올랐던 것은 세가지였다.

1. 9칸짜리 배열

2. 연결리스트

3. 트리

  배열을 사용 할 경우, 가장 큰 장점은 편하다. 그러나 단점은, 반복문과 조건문이 연결리스트, 트리를 사용하는 방법에 비해 매우 많이 들어갈 것이므로, 속도가 많이 느릴 것이다. 링크를 사용하는 연결리스트, 트리를 이용할 경우 자동적으로 배열과 반대의 장/단점을 갖는다.  

이하 소스코드. 주석참고.

 
#include<stdio.h>
#include<stdlib.h>
 
int main() // gcc는 왜 main을 void로 못 받는지 이유가 궁금하다. 
{
    int arr[9],num;
 
    for(int i=0;i<=8;i++)
    {
        scanf("%d",&num);
        arr[i]=num;    // 할당
    }
    int sum=0,tmp;
    for(int i=0;i<=8;i++)
    {
        sum=sum+arr[i];
    }
    for(int i=0;i<=7;i++)
    {
        for(int j=(i+1);j<=8;j++)    // 한 쌍을 찾는거니까 이중for문을 돌렸다. 트리오였으면 삼중for문을 사용할 듯.
        {
            tmp=arr[i]+arr[j];    // 
            if(sum-tmp==100)     // 문제의 핵심. 난 2가지를 뽑아서 전체에서 빼는 방식을 택했는데,
                                // 7개 뽑아서 더하는 방식도 무방할 듯. 단지 코드가 많이 더러워 지겠지. 
            {
                // printf("comb of arr is %d %d \n",arr[i],arr[j]);
                // 이 부분 때문에 뜨는 오류 때문에 한 시간 정도 날렸다. 
                // 백준 이용자들은 꼭 결과값만(혹은 문제에서 요구하는 것들만) 출력하는 것을 생활화해야 할 듯.
                for(int l=0;l<=7;l++)    // 빼야 하는 한 쌍을 찾은 후 정렬 시작
                {
                    if(l!=i && l!=j)    // 제외
                    {
                        for(int m=(l+1);m<=8;m++)
                        {
                            if(m!=i && m!=j)    // 제외
                            {
                                if(arr[l]>arr[m])
                                {
                                    tmp=arr[l];
                                    arr[l]=arr[m];
                                    arr[m]=tmp;
                                }
                            }
                        }            
                    }
                }
                for(int a=0;a<=8;a++)
                {
                    if(a!=i && a!=j)
                    {
                        printf("%d ",arr[a]);
                    }
                }
                return 0;
            }
        }
    }
    return 0;
}