사용자 도구

사이트 도구


ps:problems:boj:31288

캬루

ps
링크acmicpc.net/…
출처BOJ
문제 번호31288
문제명캬루
레벨실버 2
분류

해 구성하기

시간복잡도O(Σn)
인풋사이즈Σn<=3545
사용한 언어Python 3.11
제출기록31120KB / 44ms
최고기록44ms
해결날짜2024/01/30

풀이

  • 주어진 수에서 숫자 하나를 바꿔서 소수가 아닌 수로 만들어야 하는데, 이런 수를 n개를 만들어야 한다
  • 방법이야 다양하겠지만, 쉽게 떠올릴수 있는 방법은, 모든 자릿수의 합이 3의 배수인 수는 3의 배수라는 점을 이용하는 것이다.
  • 어느 자리의 숫자를 바꿔도 모든 자릿수의 합이 3의 배수가 되도록 만들수 있으니까, 이 방법만으로 3의 배수를 n개 이상 만들수 있다.
  • 실수의 여지가 있는 것은, 만들어지는 수가 0 으로 시작하지 않도록 하는 부분과, p가 1자리 수일때는 3을 만들지 않도록 해야 하는 부분이다. 내 경우 후자의 처리는 모든 자릿수의 합이 9의 배수가 되게 만든다음, 약수는 3으로 써주는 방식으로 처리했다.

코드

"""Solution code for "BOJ 31288. 캬루".

- Problem link: https://www.acmicpc.net/problem/31288
- Solution link: http://www.teferi.net/ps/problems/boj/31288

Tags: [ad hoc]
"""

import sys


def main():
    T = int(sys.stdin.readline())
    for _ in range(T):
        N, P = sys.stdin.readline().split()  # pylint: disable=unused-variable
        digit_sum = sum(int(c) for c in P)
        for i, c in enumerate(P):
            x = (int(c) - digit_sum) % 9
            if x == 0:
                x = 9
            print(f'{P[:i]}{x}{P[i+1:]} 3')


if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
X T᠎ O W I
 
ps/problems/boj/31288.txt · 마지막으로 수정됨: 2024/02/15 08:21 저자 teferi