딱지놀이( BOJ 14696 )

문제 : https://www.acmicpc.net/problem/14696

14696번: 딱지놀이

 

문제 파악하기

A와 B의 딱지놀이 결과를 출력하는 문제입니다. 딱지에는 별(★), 동그라미(●), 네모(■), 세모(▲) 중 하나의 그림이 그려져있으며 우리는 A와 B가 가지고 있는 모든 딱지의 개수를 파악하여 승패를 알아내야 합니다. 승패를 가르는 중요한 요소는 바로 그림의 가중치라고 할 수 있습니다. 모든 그림에는 각기 다른 가중치가 부여되어 있으며, 그림 사이의 대소관계는 다음과 같습니다.

별(★) > 동그라미(●) > 네모(■) > 세모(▲)

 

우리는 위의 대소관계를 구분하는 알고리즘을 만들어 문제를 해결해야 합니다. 그럼 어떤 방법을 사용할 수 있을까요? 여러가지 있지만 가장 간단한 방법을 소개해드리겠습니다.

 

문제 해결하기

대소관계를 구분하는 가장 간단한 방법은 바로 배열을 사용하는 방법입니다. 각각의 그림만큼 배열을 2개 만든 다음, 두 학생이 가진 카드 개수만큼 배열의 값을 각각 증가시켜줍니다. 그 다음 별(★)부터  세모(▲)까지 확인하면서 어느 한 학생의 카드가 많은 순간 탐색을 종료하고 결과를 출력하면 됩니다.

 

소스코드

#include <stdio.h>
#include <string.h>
#define NMAX 5
 
int T, N;
 
int nA, nB, v;
int A[NMAX], B[NMAX];
 
char f;
 
int main() {
    for(scanf("%d", &T);T>0;T--) {
        // init
        memset(A, 0, sizeof(A));
        memset(B, 0, sizeof(B));
 
        // input
        scanf("%d", &nA);
        for(int i=1;i<=nA;i++) {
            scanf("%d", &v);
            A[v]++;
        }
        scanf("%d", &nB);
        for(int i=1;i<=nB;i++) {
            scanf("%d", &v);
            B[v]++;
        }
 
        // 판별
        f = 'D';
        for(int i=4;i>0;i--) {
            if(A[i] > B[i]) {
                f = 'A';
                break;
            }
            else if(A[i] < B[i]) {
                f = 'B';
                break;
            }
        }
 
        // 출력
        printf("%c\n", f);
    }
}

후기

기본적인 구현 문제라고 생각합니다. 가중치이기 때문에 숫자를 부여하는 방식으로도 해결할 수 있다고 생각합니다. 알고리즘을 시작하는 사람들에게 추천하고 싶은 문제입니다.