[SW Expert] 6959. 이상한 나라의 덧셈게임

생각

Github - https://github.com/hellojdh/Code/blob/master/src/swexpert/d4/Q6959.java

양수가 주어진다. 예를들어 1234가 주어지면 연달아 있는 두개의 숫자를 선택한다.
23을 선택했으면 154로 만들 수 있고, 34를 선택했으면 127을 만들 수 있다.
이런식으로 두사람이 숫자를 더해주면서 번갈아 게임을 진행했을 때 1자리 숫자가 남게되면
그 차례 사람이 진다. 이긴 사람을 출력하여라.

처음 생각

다양한 풀이가 있을것 같다는 생각이든다. A,B 엘리스와 토끼가 번갈아가면서 게임을 진행하고 최선을 다해 게임에 임한다고 한다.

▶ 최선을 다하든 최선을 다하지 않고 게임에 임하든 한 자리가 될 때까지 게임의 진행 횟수는 같다.

다음 생각

그래서 처음에는 각 자리수를 모두 더한다음 그 수를 10으로 나누어 몇 번 10이상이 반복되는지 찾으려고 했지만 다음과 같은 반례가 있었다.

▶ 1189 이면 각 수를 다더하면 19가 나오고 /10을 하면 1 그리고 4자리 수이므로 기본 3번은 합쳐야 하므로 1+3으로 총 4번으로 판단을 했었다.

▶ 하지만 1189같은 수는 다음과 같이 자리수가 바뀌지 않는 즉, 수를 합쳤을 때 10이상이 되는 구간이 2번 진행이된다.

1189

289

109

19

10

1

다다음 생각

수학적으로 생각해보려다 잘 안됐지만 어찌어찌하면 위 방법으로도 풀 수는 있을 것 같다. 다시 문제로 돌아와서 어떤 숫자를 가지고 앞에서부터 더하든 뒤에서부터 더하든 중간에서부터 더하든 게임의 횟수는 같다. 더하기 연산 이기 때문이다.

다다다음 생각

따라서 앞에서부터 게임을 진행해주면서 더했을 때 10이상이라면 그 수를 더해준뒤 다음 수를 더해주는 방식으로 게임 횟수를 카운트 하였다.

방안

1) Java 풀이

package swexpert.d4;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
public class Q6959 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int tc = Integer.parseInt(br.readLine());
 
        for(int z=1;z<=tc;z++) {
            sb.append('#').append(z).append(' ');
            String t = br.readLine();
            int len = t.length();
            int sum = 0;
 
            // 어차피 수는 똑같으므로 앞에서부터 단계만 따져주자.
            int cnt = 0;
            for(int i=0;i<len;i++){
                sum += t.charAt(i)-'0';
                cnt++;
                // 2개를 더해서 2자리가 나오면 더해주기
                if(sum>=10){
                    sum = sum/10 + sum%10;
                    cnt++;
                }
            }
            // 짝수번 진행이 아니면 B의 승리 (A부터 시작이니)
            if(cnt%2!=0) sb.append('B').append('\n');
            else sb.append('A').append('\n');
        }
        System.out.println(sb);
    }// end of main
}// end of class