게임에서 강력한 기술을 사용할 수 있는 조건을 판별하는 문제를 풀어보자.
문제 : 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가 된다. 두 구간은 서로 겹치지 않고 합쳐서 전체를 덮는다.
구현 단계는 다음과 같다.
- 입력을 문자열로 읽는다.
- 길이를 구해 절반 위치
half를 정한다. [0, half)구간의 숫자 합과[half, len)구간의 숫자 합을 구한다.- 두 합을 비교해 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()로 얻고, 두 구간을 각각 선형으로 순회하며 모든 자릿수를 한 번씩 확인한다.
| |
C++ without library 코드와 설명
표준 라이브러리 컨테이너 없이 char 배열과 scanf로 같은 로직을 구현한다. 배열 크기는 제약의 8자리에 널 문자를 더한 값보다 크게 잡으며, 길이는 strlen으로 얻는다.
| |
Python 코드와 설명
input()이 개행을 제거한 문자열을 돌려주므로 len이 곧 자릿수다. 구간 합은 제너레이터 식과 sum으로 한 줄씩 쓴다.
| |
결론
자릿수 합이라는 정수론적 성질을 문자열 인덱스 두 구간으로 환원한 것이 이 풀이의 전부다. 입력이 정수 연산(%10)에 유리한 형태(매우 큰 수가 아니라 이미 수치로 가공된 값)라면 정수 방식이, 입력이 문자열로 들어오고 경계가 자릿수로 정의될 때는 문자열 방식이 더 안전하다. 같은 판단 기준은 “합 비교형” 구현 문제 전반에 쓸 수 있다.
코너 케이스 및 실수 포인트
| 케이스 | 설명 | 처리 방법 |
|---|---|---|
| 최소 입력 | 10 (자릿수 2, 1과 0) | half = 1, 합 1 ≠ 0 → READY |
| 최대 입력 | 99999999 (자릿수 8) | 양쪽 합 36으로 같음 → LUCKY, int로 충분 |
| 뒤쪽에 0 포함 | 123402 | 0을 그대로 더해 6 = 6 → LUCKY |
![Featured image of post [Algorithm] C++/Python 백준 18406번 : 럭키 스트레이트](/post/algorithm/2024-10-16-boj-18406/wordcloud_hu_65dc2a093c59a101.webp)
![[Algorithm] C++/Python 백준 15025번: Judging Moose](/post/algorithm/2024-10-16-boj-15025/wordcloud_hu_7697b7e79834cbb8.webp)
![[Algorithm] C++/Python 백준 16394번 : 홍익대학교](/post/algorithm/2024-10-16-boj-16349/wordcloud_hu_4266eabae1708b9e.webp)
![[Algorithm] C++/Python 백준 18406번 : 럭키 스트레이트](/post/algorithm/2024-10-16-boj-18406/wordcloud_hu_aa946d8bcbbb344e.webp)
![[Algorithm] C++/Python 백준 20492번: 세금](/post/algorithm/2024-10-16-boj-20492/wordcloud_hu_d26cef1474ffb2c6.webp)
![[Algorithm] C++/Python 백준 23808번 : 골뱅이 찍기 - ㅂ](/post/algorithm/2024-10-16-boj-23808/wordcloud_hu_3231d4aeea1277d9.webp)
![[Algorithm] Two Pointers Algorithm](/post/2024-10-16-two-pointers/wordcloud_hu_2ae002fe9438c7e6.webp)
![[Algorithm] C++ / Python 백준 24491번: Searching for Soulmates](/post/algorithm/2026-03-10-boj-24491-searching-for-soulmates-cpp-python-solution/wordcloud_hu_d731700bc50653bc.webp)
![[Hardware] LattePanda Alpha에 Ubuntu 16.04 LTS 설치 가이드](/post/2018-12-06-install-ubuntu-16.04-on-lattepanda/wordcloud_hu_fc536f8de2cbd4bf.webp)
![[Algorithm] C++/Python 백준 1126번 : 같은 탑](/post/algorithm/2025-02-10-boj-1126/index_hu_106e3e671c62ed4d.webp)