C언어 190제] 2011년 한국정보올림피아드 시․도지역본선 초등부 2번, 고등부 1번 나는 학급회장이다.

출처 : 반크_세계유산 경복궁

 

문제]

N명의 학생들이 모인 초등학교 반에서 학급회장 선거를 하려고 한다. 그 중 3명이 회장후보로 나왔고, 이들에 대한 선호도를 N명의 학생들 각각에게 적어내도록 하였다. 세 명의 후보는 후보 1번, 후보 2번, 후보 3번이라 한다.

모든 학생은 3명의 후보 중에서 가장 선호하는 후보에게는 3점, 두 번째로 선호하는 후보에게는 2점, 가장 선호하지 않는 후보에게는 1점을 주어야 한다. 3명의 후보에 대한 한 학생의 선호 점수는 모두 다르며, 1점, 2점, 3점이 정확히 한 번씩 나타나야 한다.

후보의 최종 점수는 학생들로부터 받은 자신의 선호도 점수를 모두 더한 값이 된다. 그러면 3명의 후보 중 가장 큰 점수를 받은 후보가 회장으로 결정된다. 단, 점수가 가장 큰 후보가 여러 명인 경우에는 3점을 더 많이 받은 후보를 회장으로 결정하고, 3점을 받은 횟수가 같은 경우에는 2점을 더 많이 받은 후보를 회장으로 결정한다. 그러나 3점과 2점을 받은 횟수가 모두 동일하면, 1점을 받은 횟수도 같을 수밖에 없어 회장을 결정하지 못하게 된다.

여러분은 선호도 투표를 통해 얻은 세 후보의 점수를 계산한 후, 유일하게 회장이 결정되는 경우에는 회장으로 결정된 후보의 번호(1, 2, 3 중 한 번호)와 최고 점수를 출력하고, 회장을 결정하지 못하는 경우에는 번호 0과 최고 점수를 출력하는 프로그램을 작성하시오.

입력
첫째 줄에는 반의 학생들의 수 N (3 ≤ N ≤ 1,000)이 주어진다. 다음 N개의 각 줄에는 각 학생이 제출한 회장후보 3명에 대한 선호 점수가 주어지는 데, 첫 번째 점수는 후보 1번에 대한 점수이고 두 번째 점수는 후보 2번에 대한 점수이고 세 번째 점수는 후보 3번에 대한 점수이다. 이 세 점수는 서로 다르며, 1, 2, 3이 정확히 한 번씩 나타난다.

출력
학생들의 선호도 투표 결과로부터, 회장이 유일하게 결정되는 경우에는 회장으로 결정된 후보의 번호와 최고 점수를 출력하고, 유일하게 결정할 수 없는 경우에는 0과 최고 점수를 출력한다.

예제 입력 1 
6
3 1 2
2 3 1
3 1 2
1 2 3
3 1 2
1 2 3
예제 출력 1 
1 13

예제 입력 2 
6
1 2 3
3 1 2
2 3 1
1 2 3
3 1 2
2 3 1
예제 출력 2 
0 12

출처 : 백준_2456번

 

참고풀이]

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h> //malloc(), free()

int main()
{
   int i,j;//인덱스 또는 반복변수
   //0행:전체합, 1행:1 개수, 2행:2개수, 3행:3개수
   //0열:최대값, 4열:최대값의 인덱스값, 1열~3열:후보점수
   //5열:인원수
   int R[4][6] = { 0 };

   //반의 학생수를 입력받는다.
   int N;
   scanf("%d", &N);
   if (N >= 3 && N <= 1000)
   {
      //N명의 투표자료를 입력받는다.
      int** M = (int **)malloc(sizeof(int*) * N);
      for (i = 0; i < N; i++)
      {
         M[i] = (int *)malloc(sizeof(int) * 3);
         for (j = 0; j < 3; j++)
            scanf("%d", &M[i][j]);
      }

      //각 후보자의 총점을 구한다.
      for (i = 0; i < N; i++)
         for (j = 0; j < 3; j++)
         {
            R[0][j+1] += M[i][j];//후보자의 총점을 구한다.
            //후보자의 각 점수의 개수를 구한다.
            if (M[i][j] == 3) R[3][j+1]++;
            else if (M[i][j] == 2) R[2][j+1]++;
            else R[1][j+1]++;
         }

      //최고점수를 구한다.
      R[0][0] = R[0][1];
      R[0][4] = 1;
      for(i=2;i<=3;i++)
         if (R[0][0] < R[0][i])
        {
            R[0][0] = R[0][i];
            R[0][4] = i;
         }
      //최고점수가 1명인지 체크한다.
      for (i = 1; i <= 3; i++)
         if (R[0][0] == R[0][i]) R[0][5]++;

      //결과를 출력한다.
      if (R[0][5] == 1)
         printf("%d %d", R[0][4], R[0][0]);
      else
      {
         //최고점수가 2인 이상이면 3번호 개수가 많은 후보가 당선
         for (i = 1; i <= 3; i++)
            if(R[0][0]==R[0][i])
                if (R[3][0] < R[3][i])
               {
                  R[3][0] = R[3][i];
                  R[3][4] = i;
               }
         //최고개수가 1명인지 체크한다.
         for (i = 1; i <= 3; i++)
            if (R[3][0] == R[3][i]) R[3][5]++;

         if (R[3][5] == 1)
            printf("%d %d", R[3][4], R[0][0]);
         else
         {
            //최고점수가 2인 이상이면 2번호 개수가 많은 후보가 당선
            for (i = 1; i <= 3; i++)
               if (R[0][0] == R[0][i])
                  if (R[2][0] < R[2][i])
                  {
                     R[2][0] = R[2][i];
                     R[2][4] = i;
                  }
            //최고개수가 1명인지 체크한다.
            for (i = 1; i <= 3; i++)
               if (R[2][0] == R[2][i]) R[2][5]++;

            if (R[2][5] == 1)
               printf("%d %d", R[2][4], R[0][0]);
            else
               printf("%d %d", 0, R[0][0]);
         }
      }

      //동적메모리를 해제한다.
      for (i = 0; i < N; i++)
         free(M[i]);
      free(M);
   }

   return 0;
}

 

참고풀이 결과]

 

 

 

 

 

대한민국의 아름다운 영토, 독도의 가을