Security 2

 

 

 

 

Problem: https://atcoder.jp/contests/abc407/tasks/abc407_c

C - Security 2

 

문제 요약

특별한 기능을 가진 버튼 A, B가 있다.

입력된 값(input)을 만들기 위해서는, A,B 버튼을 최소 몇 번 사용해야 하는가?

 

초기값: 빈 문자열(S)

버튼A: S에 0을 더한다

버튼B: S의 모든 문자에 1을 더한다

 

예시)

S: 1984

버튼A: 19840

버튼B: 20951

 

모든 문자는 (0, 1, 2, 3, 4, 5, 6, 7, 8, 9)로만 되어 있다.

---

Sample Data

Input 1: 21

Output 1: 4

(버튼A: 0) → (버튼B: 1) → (버튼A: 10) → (버튼B: 21)

 

Input 2: 407

Output 2: 17

 

Input 3: 2025524202552420255242025524

Output 3: 150

---

문제풀이

먼저, 버튼 A, B의 특성에 대해 파악해야한다.

버튼	특성
A	● 문자열 길이를 늘린다. ● 입력된(input) 숫자의 자릿수만큼 버튼A를 눌러야 한다.
B	● 숫자의 자릿수에는 영향을 주지 않는다. ● 현재까지 만들어진 모든 숫자에 영향을 준다.

 

위 특성을 기반으로 몇 가지 가정(생각)을 해볼 수 있다.

 

S = input

\( S_{i} \) = i-번째 글자

 

1. S의 길이가 N이면, 버튼A는 N번 눌러야 한다.

하지만 N번 연속해서 누르지 않는다. 왜냐하면, 중간에 버튼B를 동작시켜야 원하는 값(input)을 맞출 수 있기 때문이다.

 

2. 그렇다면 S를 만들기 위해서는 중간에 B를 몇 번 눌러야 할까?

 

먼저 \( S_{n} \)을 살펴보자. 

\( S_{n} \)을 만들기 위해서는, A를 눌러 0을 추가하고 → B를 눌러 숫자를 맞추면 된다.

즉, \( S_{n} \) 만큼 B를 누르면 된다. (이하 \( B_{n} \) )

 

\( S_{n-1} \) 은 어떨까?

\(S_{n-1} \) 에서 \( B_{n-1} \)만큼 눌렀을 거고, 

\(S_{n} \)에서 \( B_{n} \) 만큼 눌렀더니 \( S_{n-1} \)이 되었을 것이다.

따라서 다음과 같이 표현할 수 있다. \( S_{n-1} = B_{n-1} + B_{n} \)

하지만 이 값은 0 ~ 9 사이어야 한다. \( S_{n-1} = (B_{n-1} + B_{n}) \mod 10 \) 

 

이제 \( S_{n} \) 과 \( S_{n-1} \) 을 연립하면 \( B_{n-1} \) 을 구할 수 있다.

\( S_{n} = B_{n} \)

\( S_{n-1} = (B_{n-1} + B{n}) \mod 10 \)

 

\( S_{n} - S_{n-1} = B_{n} - (B_{n-1} + B_{n}) \mod 10 \)

\( S_{n} - S_{n-1} = B_{n} - B_{n-1} - B_{n} \mod 10 \)

\( S_{n} - S_{n-1} = - B_{n-1} \mod 10 \)

\( B_{n-1} \mod 10 = - (S_{n} - S_{n-1}) \)

\( B_{n-1} = (S_{n-1} - S_{n}) \mod 10 \)

\( B_{n-1} = (10 + S_{n-1} - S_{n}) \mod 10 \) (항상 0 ~ 9 이어야 하므로, 음수일 경우를 대비해서 +10을 한다)

 

우리가 구하고자 하는 것은, 버튼A와 B를 각각 누른 횟수이다.

버튼A = 문자 길이(N)

버튼B = \( B_{1} + B_{2} + ... + B_{n} \)

\( B_{i} = (10 + S_{i-1} - S_{i}) \mod 10 \)