백준 3273번 두 수의 합 [C언어]

문제 출처: https://www.acmicpc.net/problem/3273

3273번: 두 수의 합

 

 

Sol1) 수열의 값을 저장할 배열을 선언하는 방법

#include <stdio.h>

int main(){

    int n, x, cnt = 0;
    int checking[2000000] = {0};

    scanf("%d", &n);

    int seq[n];

    for(int i = 0; i < n; i++)
        scanf("%d", &seq[i]);
    

    scanf("%d", &x);

    for(int k = 0; k < n; k++){
        if(x > seq[k]){
            if(checking[x - seq[k]] == 1) //순서 바꿔줘도 무관
                cnt++;

            checking[seq[k]] = 1; //순서 바꿔줘도 무관
        }
    }

    printf("%d\n", cnt);

    return 0;
}

 

Sol2) 수열의 값을 저장할 배열 없이 푸는 방법

#include <stdio.h>

int main(){

    int checking[2000000] = {0}; //굳이 배열을 2개 만들 필요 없음.
    int n, seq_val, x, cnt = 0;

    scanf("%d", &n);

    for(int i = 0; i < n; i++){
        scanf("%d", &seq_val);

        checking[seq_val] = 1;
    }

    scanf("%d", &x);
    
    for(int k = 1; k < (x + 1) / 2; k++){ //(x + 1) / 2 -> 홀수일 떄 반올림. ceil(x / 2) or round(x / 2)도 가능.
        if(checking[k] && checking[x - k])
            cnt++;
    }

    printf("%d\n", cnt);

    return 0;
}

 

 

• 풀이 방향

순서쌍을 찾거나, 시간제한이 타이트한 문제에서는 마킹할 배열(위 코드에서는 checking 배열)을 만들 생각을 해보는 것이 좋다. 두 수의 합이 x가 되려면, 어떤 수 k와 쌍을 이루는 수 x - k가 존재해야 하기때문에 해당 값이 마킹돼 있는지 체크해 보면 되겠다.

 

• 풀이

이 문제는 수열의 값을 저장할 배열을 선언해도 되고 선언하지 않아도 된다. 선언하지 않는 편이 코드 자체는 더 간단하다. 

 

1. 수열의 값을 저장할 배열을 선언한 경우

수열 값들을 배열에 저장한 후, 수열의 값과 같은 checking배열의 인덱스의 값을 0에서 1로 바꿔준다. 그리고, 짝이 되는 x - k 인덱스의 값이 1인지를 체크한다. 1이면 cnt변수를 1 올려준다. 단, x가 해당 수열의 값보다 클 경우만 체크한다. x보다 수열의 값이 클 경우, 문제 조건에따라 수열의 값은 음수가 될 수 없으므로 어차피 만족하는 쌍을 찾을 수 없기때문이다.

 

2. 수열의 값을 저장할 배열을 선언하지 않은 경우

이 때는 들어온 입력값을 checking배열의 인덱스로 받아 해당 인덱스의 checking 배열의 값을 1로 바꿔준다. 그 후, 수열의 값은 1부터이므로 1부터 x가 짝수면 x의 절반, 홀수면 (x + 1) / 2까지 x - k의 값또한 1로 마킹 돼 있는지를 체크한다. 이 경우 k값은 x값보다 커질 수 없으므로 따로 범위를 체크할 필요는 없다.

 

• 문제에 대한 사견

O(N)으로 푸는 풀이를 떠올리기가 쉽지 않아 정답률이 낮은 것 같은 문제였다. 하지만 떠올리기만 하면 식을 세우는 과정이나 구현 과정에서 특별한 어려움 없이 풀어낼 수 있다.