어떤 숫자 n이 주어졌다고 가정해 봅시다. 게임 속 모든 캐릭터는 네 가지 체력(HP) 등급 중 하나에 속하며, 각 등급은 다음과 같이 분류됩니다.
- 카테고리 A : HP가 (4n + 1) 형태인 경우
- 카테고리 B : HP가 (4n + 3) 형태인 경우
- 카테고리 C : HP가 (4n + 2) 형태인 경우
- 카테고리 D : HP가 4n 형태인 경우
이 네 가지 카테고리는 A > B > C > D 순서로 높은 등급을 나타냅니다. 즉, 카테고리 A가 가장 높고 카테고리 D가 가장 낮습니다.
게임을 진행하는 동안 플레이어는 캐릭터의 HP를 늘릴 수 있습니다. 이때 아말(Amal)은 자신의 HP를 최대 2까지만 증가시키려 합니다(즉, 0, 1 또는 2만큼). 우리가 찾아야 할 것은 HP를 얼마나 증가시켜야 가장 높은 카테고리에 도달할 수 있는지입니다.
예제
예를 들어 n = 98이라면 출력은 "1 B"가 됩니다. 그 이유는 다음과 같습니다.
- 98은 (4 × 24 + 2) 형태이므로 현재 카테고리 C에 해당합니다.
- HP를 1만큼 증가시키면 99가 되어 카테고리 B로 승급합니다.
- 반면 2만큼 증가시키면 100이 되는데, 이는 (4 × 25) 형태의 카테고리 D로 오히려 하락하게 됩니다.
따라서 달성 가능한 최대 카테고리는 B이며, 필요한 증가량은 1입니다.
풀이 접근 방법
이 문제는 n을 4로 나눈 나머지(n mod 4)에 따라 간단히 해결할 수 있습니다.
if n mod 4 is same as 2, then:
return "1 B"
Otherwise
return |(n mod 4) - 1| and 'A'핵심 로직 설명
- n mod 4가 2라면(카테고리 C), 1을 더하면 곧바로 카테고리 B가 되므로 "1 B"를 반환합니다.
- 그 외의 경우(카테고리 A, B, D), |(n mod 4) − 1|만큼 더하면 항상 카테고리 A에 도달할 수 있습니다.
- n mod 4 = 0 (D) → 1 증가
- n mod 4 = 1 (A) → 0 증가
- n mod 4 = 3 (B) → 2 증가
C++ 구현 예제
다음 코드를 통해 실제 구현을 확인해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
void solve(int n){
if (n % 4 == 2)
cout << "1 B";
else
cout << abs(n % 4 - 1) << " A";
}
int main(){
int n = 98;
solve(n);
}입력
98
출력
1 B
이처럼 나머지 연산 하나만으로 각 카테고리를 판별하고, 최소한의 증가량으로 최상위 등급을 계산할 수 있습니다. 시간 복잡도는 O(1)로 매우 효율적입니다.