반응형
문제
https://www.acmicpc.net/problem/15829
풀이
문제와 힌트를 보면 쉽게 풀 수 있는 문제라고 생각할 수 있다.
하지만 문자열의 길이가 최대 50이다. 이는 $31^49$를 구해주어야 한다. Swift에서는 Big Integer를 지원하지 않는데 어떻게 풀이할 수 있을까?
먼저 모듈러 연산에 대해 이해하고 있어야 한다.
- $(a + b) \mod M = ((a \mod M) + (b \mod M)) \mod M$
- $(a - b) \mod M = ((a \mod M) - (b \mod M)) \mod M $
- $(a \times b) \mod M = ((a \mod M) \times (b \mod M)) \mod M $
의 성질을 알아야 한다.
이는 다른 블로그나 위키에 잘 정리된 문서가 많아서 패스하고..
이를 알면 나누어야 할 값이 1234567891 이라는 것을 알기 때문에 오버플로우 문제를 피할 수 있다.
마지막으로 a, b, c 와 같은 소문자 알파벳을 1, 2, 3과 같은 정수형으로 치환해주어야 한다.
Character 자료형의 asciiValue 프로퍼티로 구할 수 있다.
a의 ascii 값은 97이므로, a를 1로 치환하기 위해서는 a.asciiValue - 96을 해주면 된다.
나머지 알파벳들도 아스키 값이 1씩 증가하는 형태이므로, 고차함수 map을 사용해 입력받은 문자열을 정수형의 배열로 치환해주었다.
소스코드
후기
BigInt를 지원하는 언어였다면 더 쉽게 풀 수 있는 문제였다.
지원을 안한다면 모듈러 연산에 대한 이해가 있어야 한다.
반응형
'PS > 백준' 카테고리의 다른 글
[BOJ] 백준 1676 팩토리얼 0의 개수 (Swift) (0) | 2024.01.07 |
---|---|
[BOJ] 백준 2609 최대공약수와 최소공배수 (Swift) (0) | 2024.01.03 |
[BOJ] 백준 2751 수 정렬하기 2 (Swift) (0) | 2023.12.31 |
[BOJ] 백준 4153 직각삼각형 (Swift) (1) | 2023.12.30 |
[BOJ] 백준 1259 팰린드롬수 (Swift) (0) | 2023.12.30 |