CodeTree Carry 피하기

풀이

1. 두 수를 더했을 때 Carry가 발생하는지 확인하기 위한 메서드를 정의한다. 두 변수를 10으로 나눈 나머지를 더하여 10보다 커지는지 확인하고 두 변수를 10으로 나눈 몫으로 각각의 변수를 업데이트한다. 하나의 변수라도 0이 될 때까지 Carryrk 발생하지 않으면 True를 리턴한다.
2. 백트래킹 알고리즘을 활용한다.

코드

import java.io.*;

public class Main {
    static int n;
    static int[] nums;
    static int result = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = Integer.parseInt(br.readLine());
        }
        backTracking(0, 0, 0);
        System.out.println(result);
    }

    public static void backTracking(int start, int sum, int count) {
        result = Math.max(result, count);

        for (int i = start; i < nums.length; i++) {
            if (isNotCarry(sum, nums[i])) {
                backTracking(i + 1, sum + nums[i], count + 1);
            }
        }
    }

    public static boolean isNotCarry(int a, int b) {
        while (a != 0 || b != 0) {
            int digit_a = a % 10;
            int digit_b = b % 10;

            if (digit_a + digit_b >= 10) {
                return false;
            }

            a /= 10;
            b /= 10;
        }
        return true;
    }
}