[BOJ 23977] 백준 23977번 - To Find Password

		Zero One Algorithm Contest 2021 풀이
A		[BOJ 23971] ZOAC 4
B		[BOJ 23972] 악마의 제안
C		[BOJ 23973] 표적지 옮기기
D		[BOJ 23974] 짝수 게임
F		[BOJ 23976] 문자열 나누기
G		[BOJ 23977] To Find Password
H		[BOJ 23978] 급상승

1. 문제

$23977$. To Find Password (Zero One Algorithm Contest 2021 Open Contest G번)

백준 23977번 - To Find Password (https://www.acmicpc.net/problem/23977)

2. 풀이

비밀번호를 $X$라고 둔다. 입력을

$K$ $N$
$A_1$ $A_2$ $A_3$ $…$ $A_N$

이라고 가정한다. 그럼 ($m \rightarrow$ 임의의 몫)

$X = A_1 \times m_1 + (A_1 - K)$

$X = A_2 \times m_2 + (A_2 - K)$

$…$

$X = A_N \times m_N + (A_N - K)$

이 식들을 다음과 같이 변형할 수 있다.

$X $ $= A_1 \times m_1 + (A_1 - K) $ $= A_1 \times (m_1 + 1) - K$ $X $ $= A_2 \times m_2 + (A_2 - K) $ $= A_2 \times (m_2 + 1) - K$ $…$ $X $ $= A_N \times m_N + (A_N - K) $ $= A_N \times (m_N + 1) - K$

따라서 $X$는 $A_1, A_2, A_3, … , A_N$의 최소공배수에서 $K$를 뺀 값이다. $K \lt min(A_i)$ 이고 $A_1\sim A_N$의 최소공배수는 $min(A_i)$보다 크거나 같으므로 최소공배수에서 $K$를 빼는 작업은 문제가 없다.

3. 채점 결과

4. 회고

최소공배수를 구하는 중간 곱하기 과정에서 integer가 넘어갈 수 있다는 점을 간과하여 WA를 받았다.

5. 코드