[코드트리/NOVICE MID] Carry 피하기 2 (JAVA)

🔺 문제

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int max = Integer.MIN_VALUE;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        int N = Integer.parseInt(br.readLine());
        int[] arr = new int[N];
 
        for(int i = 0 ; i < N ; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }
 
        for(int i = 0 ; i < N - 2 ; i++) {
            for(int j = i + 1 ; j < N - 1 ; j++) {
                for(int k = j + 1 ; k < N ; k++) {
                    if(isNotCarry(arr[i], arr[j], arr[k])) { // carry가 발생하지 않는다면, 최댓값 갱신
                        max = Math.max(max, arr[i] + arr[j] + arr[k]);
                    }
                }
            }
        }
        
        System.out.println((max == Integer.MIN_VALUE) ? -1 : max);
    }
    
    // 숫자 3개에서 carry가 발생하는지 확인 메소드
    private static boolean isNotCarry(int a, int b, int c) {
        for(int i = 0 ; i < 5 ; i++) {
            if((a % 10 + b % 10 + c % 10) >= 10) {
                return false;
            }
            a /= 10;
            b /= 10;
            c /= 10;
        }
 
        return true;
    }
}

 

 

 

🧩  해결 아이디어

• 완전탐색

- 일, 십, 백, 천의 자리를 각각 더하며 carry가 발생하는지 확인한다.

- carry가 발생하지 않고, 3개의 숫자의 합이 현재 정답값보다 크다면, 정답을 갱신한다.

 

 

---

💬 느낀 점

더 빠르게 풀 수 있었는데 이상한 데에서 헤매가지고 시간을 오래 걸려 풀었다...ㅠ

담엔 집중해서 더 빠르게 풀 수 있게ㅠㅠ

 

1회독	2회독	3회독	4회독	5회독
V