카드 바꾸기( BOJ 25401 )

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

25401번: 카드 바꾸기

 

문제 파악하기

N개의 카드를 등차수열로 만드는 문제입니다. 공차는 음수, 0, 양수 모두 될 수 있으며, 주어진 N개의 숫자 중 일부분을 바꿔 등차수열로 만들었을 때, 바꾼 카드 수의 최솟값을 구해야 합니다. 등차 수열을 만드는 가장 간단한 방법은 모든 숫자를 하나의 숫자로 통일하는 것입니다. 하지만 이 방법은 비효율적이기에 조금 더 효율적인 방법이 필요하며, 이 때에는 2개의 숫자를 기준으로 활용할 수 있습니다.

 

문제 해결하기

입력되는 N개의 숫자는 최대 500개입니다. 따라서, 우리는 두 숫자를 기준으로 설정하는 중첩 반복문을 활용할 수 있습니다. 그리고 2개의 숫자를 기준으로 설정하면 다음은 간단합니다. 공차가 정수로 만들어질 수 있는지 확인한 다음, 만들 수 있다면 첫 항을 구한 다음, 현재 수열과 비교해서 다른 숫자의 개수를 세면 됩니다. 두 수를 사용해 만들 수 있는 모든 수열을 확인하고 그 중 최솟값을 구하면 우리가 원하는 결괏값을 얻게 됩니다.

 

소스코드

#include <stdio.h>
#include <algorithm>
#define NMAX 505
using namespace std;
 
int N;
int inp[NMAX];
 
int d, val, tcnt, ret;
 
int main() {
    scanf("%d", &N);
    for(int i=1;i<=N;i++) scanf("%d", &inp[i]);
    
    ret = N-1;
    for(int i=1;i<=N;i++) {
        for(int j=i+1;j<=N;j++) {
            // inp[i] + (j-i)*d = inp[j]
            if((inp[j]-inp[i])%(j-i) != 0) continue;
            
            d = (inp[j]-inp[i])/(j-i);
            
            val = inp[i] - (i-1)*d;
            tcnt = 0;
            for(int k=1;k<=N;k++) {
                if(val != inp[k]) tcnt++;
                
                val += d;
            }
            
            ret = min( ret, tcnt );
        }
    }
    
    printf("%d", ret);
}
 

후기

정올 초등학교 문제답게 어려운 개념이 필요하지 않았습니다. 정올의 맛을 느낄 수 있기에 정올을 소개할 때, 사용할 수 있는 간단한 문제라고 생각합니다. 문법을 마친 다음, 정올을 시작하는 사람에게 추천하고 싶은 문제입니다.