[백준 2309번] #1. 일곱 난쟁이 - 처음으로 해본 PS (C++)

 

 

 

 

처음으로 백준 온라인 저지에서 문제 같은 문제를 풀어보았습니다.

 

 

어떤 문제로 시작하는 것이 좋을까 구글링 하다가

 

한국정보올림피아드 초등부 문제부터 풀어보는 것이 좋다고 해서 무작정 찾아 들어가 푼 문제입니다.

 

 

 

 

 

알고 보니 이 문제는 완전 탐색(Brute Force) 문제라던데

 

필자는 아직 안 배운 내용이라 그냥 선택 정렬 알고리즘으로 풀었습니다.

 

 

나중에 실력을 더 쌓고 완전 탐색으로 다시 한 번 풀어보겠습니다.

 

어쨌든 처음으로 푼 문제라는 것이 중요하니까!!

 

 

 

 

<1> 문제

 

 

www.acmicpc.net/problem/2309

2309번: 일곱 난쟁이

 

왕비를 피해 일곱 난쟁이들과 함께 평화롭게 생활하고 있던 백설공주에게 위기가 찾아왔다.

 

일과를 마치고 돌아온 난쟁이가 일곱 명이 아닌 아홉 명이었던 것이다. (?!)

 

 

아홉 명의 난쟁이는 모두 자신이 "백설 공주와 일곱 난쟁이"의 주인공이라고 주장했다.

 

뛰어난 수학적 직관력을 가지고 있던 백설공주는, 다행스럽게도 일곱 난쟁이의 키의 합이 100이 됨을 기억해 냈다.

 

 

아홉 난쟁이의 키가 주어졌을 때, 백설공주를 도와 일곱 난쟁이를 찾는 프로그램을 작성하시오.

 

 

 

 

 

 

<2> 풀이

 

9명의 난쟁이 중 진짜 7명의 키가 100이란 말은

 

(나머지 2명의 키) = (9명의 난쟁이 키 합) - 100

 

즉, 9명의 난쟁이 키를 입력 받을 때부터 모두 다 더하고 100을 뺀 값과

 

9명 중 2명을 뽑아 그 키들을 더한 값이 같은지 확인해보면 된다는 소리입니다.

 

이중 반복문에 조건문이 들어가겠군요.

 

 

이후 그 가짜 난쟁이 2명을 제외한 나머지 7명의 키를 새로운 배열에 저장하고

 

선택정렬 알고리즘으로 재배치시켜 출력하였습니다.

 

 

 

 

 

<3> 코드

 

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


// 선택정렬 알고리즘을 구현한 두 개의 함수
int getMinIndexInRange(int* data, int n, int begin, int end)
{
  int minIndex = begin;
  int minValue = data[begin];

  for (int i = begin; i < n; i++)
  {
    if (minValue > data[i])
    {
      minValue = data[i];
      minIndex = i;
    }
  }
  return minIndex;
}

void selectionSort(int* data, int n)
{
  for (int i = 0; i < n-1; i++)
  {
    int minIndex = getMinIndexInRange(data, n, i, n-1);
    int temp = 0;

    temp = data[minIndex];
    data[minIndex] = data[i];
    data[i] = temp;
  }
}


// 메인 함수
int main()
{
  int tallSum = -100;
  int* tall = NULL;
  int* tall2 = NULL;

  tall = new int[9];
  tall2 = new int[7];
  
  // 난쟁이들 키를 입력 받을때부터 더해 합을 tallSum변수에 저장
  for (int i = 0; i < 9; i++)
  {
    scanf("%d", &tall[i]);
    tallSum += tall[i];
  }

  // 이중 반복문으로 두 명의 가짜 난쟁이를 탐색
  for (int i = 0; i < 9; i++) {
    for (int j = i+1; j < 9; j++) {
      if(tall[i] + tall[j] == tallSum) {
        tall[i] = 0; tall[j] = 0;
        goto EXIT;
      }
    }
  }

EXIT:
  // tall2 새 배열에 진짜 7명의 난쟁이들의 키를 대입
  int k = 0;
  int l = 0;
  while (k < 9)
  {
    if (tall[k] != 0)
    {
      tall2[l] = tall[k];
      l++;
    }
    k++;
  }

  // 선탣 정렬 알고리즘으로 키를 오름차순으로 나열
  selectionSort(tall2, 7);

  for (int i = 0; i < 7; i++)
  {
    cout << tall2[i] << endl;
  }

  delete[] tall;
  delete[] tall2;

  return 0;
}

 

 

 

 

 

 

 

<3> 아쉬운 점

(더 효율적으로 어떻게 풀 수 있었을까)

 

 

오름차순으로 먼저 재배치하고 가짜 2명을 솎아냈으면

 

배열을 1개만 썼어도 되었을 아쉬움이 남습니다.

 

시간 되면 나중에 꼭 다시 풀어보고 이 코드랑 비교해보고 싶네요.