Featured image of post [Algorithm] C++/Python 백준 18406번 : 럭키 스트레이트

[Algorithm] C++/Python 백준 18406번 : 럭키 스트레이트

백준 18406 럭키 스트레이트 문제는 주어진 점수의 자릿수를 절반으로 나누어 각 부분의 자릿수 합이 같은지 판단하는 알고리즘 문제입니다. C++ 및 Python으로 구현하며 문자열 처리를 활용합니다. 각 합이 같으면 LUCKY, 다르면 READY를 출력합니다.

게임에서 강력한 기술을 사용할 수 있는 조건을 판별하는 문제를 풀어보자.

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

문제 설명

어떤 게임에서 아웃복서 캐릭터는 “럭키 스트레이트"라는 강력한 기술을 가지고 있다. 하지만 이 기술은 언제나 사용할 수 있는 것이 아니라, 현재 캐릭터의 점수가 특정 조건을 만족할 때만 사용할 수 있다.

그 조건은 현재 점수 N의 자릿수를 반으로 나누어, 왼쪽 부분의 자릿수 합과 오른쪽 부분의 자릿수 합이 동일한 경우이다. 예를 들어, 점수 N이 123402라면 왼쪽 세 자리 숫자의 합은 1 + 2 + 3 = 6이고, 오른쪽 세 자리 숫자의 합은 4 + 0 + 2 = 6이므로 두 합이 같다. 따라서 이 경우에는 “럭키 스트레이트"를 사용할 수 있다.

현재 점수 N이 주어졌을 때, “럭키 스트레이트"를 사용할 수 있는 상태인지 판별하는 프로그램을 작성하시오. 사용할 수 있다면 "LUCKY"를, 사용할 수 없다면 "READY"를 출력한다. 단, 점수 N의 자릿수는 항상 짝수이며, 10 ≤ N ≤ 99,999,999이다.

학습 목표

  • 숫자를 정수가 아닌 문자열로 다루면 자릿수 접근이 인덱싱 한 번으로 끝나는 이유를 설명할 수 있다.
  • 문제 제약(자릿수 짝수, 최대 8자리)에서 배열 크기·자료형·시간 복잡도를 직접 도출할 수 있다.
  • 문자열 방식과 정수 연산(%10, /10) 방식을 비교해 어느 쪽이 이 문제에 맞는지 판단할 수 있다.

접근 방식

이 문제의 본질은 “정수 N의 자릿수를 정확히 반으로 가른다"는 연산이다. 정수 상태에서는 전체 자릿수를 모르면 중간 경계를 잡기 어렵다. 반면 입력을 문자열로 받으면 길이 len만 알면 앞쪽 len/2개와 뒤쪽 len/2개로 곧바로 나뉘고, 각 문자 c는 c - '0'으로 해당 숫자가 된다. 문제가 자릿수가 항상 짝수라고 보장하므로 len/2는 나머지 없이 정확히 절반이며, 가운데 자릿수를 어느 쪽에 넣을지 같은 홀수 길이 문제는 생기지 않는다.

정당성은 단순하다. 두 합 sum_left와 sum_right는 각각 [0, half)와 [half, len) 구간의 숫자를 한 번씩만 더하므로 모든 자릿수가 정확히 한 번 계산되고, 두 값이 같을 때만 LUCKY가 된다. 두 구간은 서로 겹치지 않고 합쳐서 전체를 덮는다.

구현 단계는 다음과 같다.

  1. 입력을 문자열로 읽는다.
  2. 길이를 구해 절반 위치 half를 정한다.
  3. [0, half) 구간의 숫자 합과 [half, len) 구간의 숫자 합을 구한다.
  4. 두 합을 비교해 LUCKY 또는 READY를 출력한다.

시간 복잡도는 자릿수를 d라 할 때 O(d)이고, 문제 제약상 d ≤ 8이므로 사실상 상수 시간이다. 추가 메모리도 합 변수 두 개뿐이라 O(1)이다. 합의 최댓값은 한쪽이 최대 4자리이므로 9×4 = 36이며, int는 물론 char로도 충분히 담긴다.

문자열 방식과 정수 연산 방식의 비교

정수로 읽은 뒤 n % 10, n /= 10을 반복해 자릿수를 뽑는 방식도 가능하다. 이 방식은 뒤에서부터 숫자를 얻으므로 “뒤쪽 절반"의 합은 자릿수를 센 뒤 d/2번 뽑아 구하고 나머지를 앞쪽 합으로 처리해야 한다. 먼저 전체 자릿수 d를 세는 순회가 한 번 더 필요하고 경계 계산에서 off-by-one 실수가 나기 쉽다. 문자열 방식은 입력 형태 그대로 인덱스로 구간을 가르므로 구현이 짧고 경계가 명확하다. 입력이 8자리 이하라서 성능 차이는 없으므로, 실수 가능성이 낮은 문자열 방식이 이 문제에 더 알맞다.

흔한 오해와 함정

  • 정수로 읽고 길이를 log10으로 구하는 방식: 부동소수점 오차로 경계 자릿수에서 길이가 틀릴 수 있다. 문자열 길이를 쓰면 이 위험이 없다.
  • 앞자리 0 걱정: 입력은 10 이상의 정수라 선행 0이 없다. 다만 123402처럼 뒤쪽 절반에 0이 들어가는 경우(4+0+2)는 정상적으로 0을 더하면 된다.
  • 합이 같으면 숫자도 같다는 착각: 1230과 2112처럼 두 구간의 합이 각각 같아도 자리 배치는 다를 수 있다. 문제는 합만 비교하므로 배치는 무관하다.
  • 개행 문자 처리: C 방식 scanf("%s")는 공백·개행에서 끊기므로 안전하지만, fgets로 읽으면 끝의 개행 문자(\n)가 길이에 포함되어 half가 틀어진다.

C++ 코드와 설명

std::string으로 입력을 받아 cin >> N 한 줄로 읽는다. 길이는 length()로 얻고, 두 구간을 각각 선형으로 순회하며 모든 자릿수를 한 번씩 확인한다.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <iostream>
#include <string>

int main() {
    std::string N;
    std::cin >> N; // 점수 N을 문자열로 입력받는다.

    int length = N.length();
    int half = length / 2;
    int sum_left = 0, sum_right = 0;

    // 왼쪽 부분 자릿수 합 계산
    for (int i = 0; i < half; ++i) {
        sum_left += N[i] - '0'; // 문자형 숫자를 정수형으로 변환하여 합산
    }

    // 오른쪽 부분 자릿수 합 계산
    for (int i = half; i < length; ++i) {
        sum_right += N[i] - '0';
    }

    // 두 합을 비교하여 결과 출력
    if (sum_left == sum_right) {
        std::cout << "LUCKY" << std::endl;
    } else {
        std::cout << "READY" << std::endl;
    }

    return 0;
}

C++ without library 코드와 설명

표준 라이브러리 컨테이너 없이 char 배열과 scanf로 같은 로직을 구현한다. 배열 크기는 제약의 8자리에 널 문자를 더한 값보다 크게 잡으며, 길이는 strlen으로 얻는다.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <stdio.h>
#include <string.h>

int main() {
    char N[16]; // 최대 8자리 + 널 문자가 들어가는 여유 있는 크기
    scanf("%s", N); // 문자열로 입력받기

    int length = strlen(N);
    int half = length / 2;
    int sum_left = 0, sum_right = 0;

    // 왼쪽 부분 자릿수 합 계산
    for (int i = 0; i < half; ++i) {
        sum_left += N[i] - '0'; // 문자형 숫자를 정수로 변환하여 합산
    }

    // 오른쪽 부분 자릿수 합 계산
    for (int i = half; i < length; ++i) {
        sum_right += N[i] - '0';
    }

    // 두 합을 비교하여 결과 출력
    if (sum_left == sum_right) {
        printf("LUCKY\n");
    } else {
        printf("READY\n");
    }

    return 0;
}

Python 코드와 설명

input()이 개행을 제거한 문자열을 돌려주므로 len이 곧 자릿수다. 구간 합은 제너레이터 식과 sum으로 한 줄씩 쓴다.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
N = input()  # 점수 N을 문자열로 입력받음

length = len(N)
half = length // 2
sum_left = sum(int(N[i]) for i in range(half))      # 왼쪽 부분 자릿수 합
sum_right = sum(int(N[i]) for i in range(half, length))  # 오른쪽 부분 자릿수 합

# 두 합을 비교하여 결과 출력
if sum_left == sum_right:
    print("LUCKY")
else:
    print("READY")

결론

자릿수 합이라는 정수론적 성질을 문자열 인덱스 두 구간으로 환원한 것이 이 풀이의 전부다. 입력이 정수 연산(%10)에 유리한 형태(매우 큰 수가 아니라 이미 수치로 가공된 값)라면 정수 방식이, 입력이 문자열로 들어오고 경계가 자릿수로 정의될 때는 문자열 방식이 더 안전하다. 같은 판단 기준은 “합 비교형” 구현 문제 전반에 쓸 수 있다.

코너 케이스 및 실수 포인트

케이스설명처리 방법
최소 입력10 (자릿수 2, 1과 0)half = 1, 합 1 ≠ 0 → READY
최대 입력99999999 (자릿수 8)양쪽 합 36으로 같음 → LUCKY, int로 충분
뒤쪽에 0 포함1234020을 그대로 더해 6 = 6 → LUCKY