BOJ 25180 - 썸 팰린드롬 (C++)

https://www.acmicpc.net/problem/25180

문제를 푼 날짜: 25. 05. 22.

#math #greedy

아이디어

팰린드롬을 만들 때 가장 큰 숫자 9를 최대한 활용하면 자릿수를 최소화할 수 있다.

• 앞뒤로 9를 한 번씩 추가하면(총 2자리 추가) 자리 합이 $18$만큼 올라감.
• 따라서 우선 $\frac{N}{18}$번 만큼 앞뒤에 9를 붙여준다.

세부 풀이 과정

1. $p = \displaystyle\left\lfloor \frac{N}{18} \right\rfloor$

   • 이때까지 추가된 자리 수는 $2p$

2. 나머지 $r = N \bmod 18$ 에 따라 추가 자리 수를 더함

   • $r=0$

     • 더할 필요 없음 → $+0$

   • $0 < r \le 9$

     • 가운데 한 자리만 추가 → $+1$

   • $10 \le r < 18$

     • $r$ 짝수 → 앞뒤에 한 번씩 추가 → $+2$
     • $r$ 홀수 → 앞뒤 + 가운데 한 자리 → $+3$

최종 답은

내 코드

#include <iostream>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    cin >> N;

    int ans = (N / 18) * 2;

    if(N % 18 == 0) cout << ans;
    else if(N % 18 <= 9) cout << ans + 1;
    else if((N % 18) % 2 == 0) cout << ans + 2;
    else cout << ans + 3;

    return 0;
}