행복( BOJ 15969 )

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

15969번: 행복

 

문제 파악하기

N개의 학생들의 점수 중 최댓값과 최솟값을 찾아내는 문제입니다. 알고리즘을 공부하는 학생들이 가장 먼저 배우는 알고리즘이라고 할 수 있는 최댓값/최솟값 탐색 문제라고 할 수 있습니다.

 

문제 해결하기

최댓값과 최솟값을 찾는 방법에는 여러가지 있습니다. 다만, 이번 문제에서는 가장 기본적인 방법인 초깃값 설정 후 탐색을 통한 방법을 소개해드리겠습니다. N개의 숫자 중 최솟값과 최댓값을 찾기 위해서는 N개의 숫자를 살펴보면서 현재 숫자가 지금까지 확인한 숫자 중 최댓값인지 최솟값인지 판단하는 과정이 필요합니다. 이는 조건문을 통해 손쉽게 구할 수 있습니다. 만약 최댓값보다 현재 확인하는 숫자가 더 크다면 최댓값에 저장한 값을 현재 숫자로 바꿔주고, 반대로 최솟값보다 현재 확인하는 숫자가 더 작다면 최솟값에 저장한 값을 현재 숫자로 바꿔주면 됩니다.

 

다만, 이 알고리즘에서 중요한 건 초깃값 설정입니다. 최댓값과 최솟값을 저장하는 변수는 어떤 값으로 초기화해야 알고리즘에 영향을 미치지 않을까요? 바로 최솟값에는 엄청 큰 값, 최댓값에는 엄청 작은 값을 넣으면 됩니다. 여기서 말하는 엄청 큰 값과 엄청 작은 값은 알고리즘을 수행하면서 나올 수 없는 값들을 의미합니다. 이 문제의 경우, 학생들의 점수는 0~1000점 사이라고 합니다. 그렇다면 최솟값에는 학생들의 점수로 절대 나올 수 없는 엄청 큰 숫자로 1001을, 최댓값에는 나올 수 없는 엄청 작은 숫자인 -1로 초기화하면 됩니다. 물론 초기화하는 방법에는 여러가지 있다는 걸 기억하시길 바랍니다.

 

소스코드

#include <stdio.h>
 
int N, t;
int vmax, vmin;
 
int main() {
    // init
    vmax = 0; vmin = 1001;
    
    // solve
    scanf("%d", &N);
    for(int i=1;i<=N;i++) {
        scanf("%d", &t);
 
        if(t < vmin) vmin = t;
        if(t > vmax) vmax = t;
    }
 
    printf("%d", vmax - vmin);
}

후기

정말 기본적인 알고리즘 문제입니다. 알고리즘에 대해 처음 배우는 사람에게 추천하고 싶은 문제입니다.