[자바] 백준 1323 - 숫자 연결하기 (java)

 문제 : boj1323

---

 

필요 알고리즘 개념

• 수학, 정수론
  
  • 나머지 연산의 법칙을 활용하는 수학문제이다.
• 비둘기집의 원리
  • 불가능한 경우를 알기 위해 비둘기집의 원리를 사용해야 한다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

---

 

풀이

  N이 10억까지 가능한데, 이걸 3번만 붙여도 long 으로 표현 가능한 수치를 넘어간다. BigInteger를 사용해 뭔가를 구하게되면 결국 문자열로 처리하는 것이므로 연산 속도가 엄청나게 느려진다. 그러므로 int면 좋겠지만, 안된다면 적어도 long 타입이 표현 가능한 범위 이내로 처리하는 방법이 있다면 그걸 찾는게 좋다.

 

  N=1234, K=3 이라고 해보자. 그럼 이 문제는 다음과 같이 진행 가능하다.

1. 1234가 3으로 나누어떨어짐? -> X

2. 12341234가 3으로 나누어떨어짐? -> X

3. 123412341234가 3으로 나누어떨어짐? -> ㅇㅋ. 그러니 3이 답!

 

그럼 저렇게 N을 이어붙이는건 결국

N' = N * (10^(N의 자리수)) + N

이라고 볼 수 있다. 12341234 = 1234 * (10^4) + 1234 = 12340000 + 1234 라는 얘기이다.

그 다음 수인 N'' = 123412341234 = (1234 * (10^4) + 1234) * (10^4) + 1234 처럼 계속 저게 이어진다.

 

  그리고 나머지 연산에는 다음과 같은 법칙이 있다.

 

  위의 법칙이 뭘 뜻하냐면, 아무튼 중간중간 존재하는 이 문제의 모든 곱셈과 나눗셈할 값들을 K로 나눈 나머지만 가지고 계산해도 답 계산하는데 문제가 없다는 얘기이다.

즉, N = 1234, K = 3 일 때, 그냥 미리 N을 K로 나눈 나머지인 1만 가지고 있어도 된다. 10^(N의 자리수)는 원래 N을 가지고 구해야 하긴하는데, 10^4 = 1000이고, 이것도 K로 나눈 나머지인 1만 가지고 있어도 된다. 연산의 결과도 K로 나눠도 된다. 그럼 과정은 아래와 같다.

 

1. 1이 3으로 나누어떨어짐? -> X

2. 11이 3으로 나누어덜어짐? -> X (그리고 결과인 11도 3으로 나눈 나머지만 가지고 있어도 된다. 11%3 = 2)

3. 21('2'에서 남은 것에다가 (10^4)%3을 곱하고 (1234%3)을 더한것)이 3으로 나누어떨어짐? -> ㅇㅋ. 그러니 3이 답!

 

  마지막으로 '아무리 써도 불가능할 경우에는 -1을 출력' 부분을 처리해보자. 당연히 무한대로 진행하면 시간초과다. 그렇다고 일정한 횟수만큼 진행되면 멈춘다는 너무 하드코딩스럽고, 상한치를 정하기 쉽지 않다. 아이디어는 매번 계산한 결과도 K로 나눈 나머지만 가지고 있으면 된다는 점이다. 계산 결과의 중간에 동일한 값이 2번 나오는 경우 무조건적으로 사이클이 생긴다는 점을 생각해볼 수 있다. 예를들어 2번째 계산 결과가 3이었는데, 1200번째 계산 결과도 3이다. 그럼 그 이후로는 3번째~1200번째까지 나왔던 결과가 순서대로 나오면서 사이클로 무한히 계속될 것임을 생각할 수 있다. (비둘기집의 원리)

 

  K로 나눈 나머지는 항상 K 미만이고, K의 최대치는 100,000이다. 따라서 중복체크는 1부터 99999까지만 하면 된다. 해당 수가 한번이라도 더 나왔다면 거기서 -1을 출력해주면 된다.

 

결과적으로 코드는 아래와 같다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws Exception {
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        new Main().solution(n, k);
    }

    public void solution(int n, int k) throws Exception {
        int len = String.valueOf(n).length();	// N의 자리수 계산
        long mult = 1;
        for (int i = 0; i < len; i++) mult*=10;	// mult = 10^(N의 자리수)
        mult %= k;	// 10^(N의자리수) % K 만 남겨둬도 된다.

        int cnt = 1;
        Set<Long> set = new HashSet<>();
        long proc = (n%=k);	// N도 다는 필요없고, N%K만 남겨둬도 된다.
        set.add(proc);	// 사이클 여부 판정용도

        while (true) {
            if (proc == 0) break;	// 나누어떨어지면 답을 찾은 것임.
            cnt++;	// 답으로 출력할 횟수
            proc *= mult;	// N' = N*(10^(N의 자리수))
            proc += n;	// N' += N
            proc %= k;	// N' %= K
            if (set.contains(proc)) {	// 사이클 찾았으면 -1 출력하고 멈춤
                System.out.println(-1);
                return;
            }
            set.add(proc);
        }
        System.out.println(cnt);
    }
}

 

  추가로 근데 어차피 K^2 도 int형으로 표현 불가하다. 그렇다면 어쨌든 long형 내로 표현 가능한 범위 내에서  % 연산도 줄일수록 더 효율적이다. 이하 코드는 long 범위를 넘지 않는 선에서 % 연산도 어느정도 제외해서 아주 약간 더 최적화한 코드이다. (는 4ms 밖에 차이 안났다. 쳇)

 

---

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws Exception {
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        new Main().solution(n, k);
    }

    public void solution(int n, int k) throws Exception {
        int len = String.valueOf(n).length();
        long mult = 1;
        for (int i = 0; i < len; i++) mult*=10;
        mult %= k;

        int cnt = 1;
        Set<Long> set = new HashSet<>();
        long proc = (n%=k);
        set.add(proc);

        while (true) {
            if (proc == 0) break;
            cnt++;
            proc *= mult;
            proc += n;
            proc %= k;
            if (set.contains(proc)) {
                System.out.println(-1);
                return;
            }
            set.add(proc);
        }
        System.out.println(cnt);
    }
}