1491. 원재의 벽 꾸미기

문제 출처 : https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV2b9AkKACkBBASw&categoryId=AV2b9AkKACkBBASw&categoryType=CODE

음... 오버플로우 대응 문제 였습니다.

시간을 줄이기 위해서는 몇가지 생각을 하면 됩니다.

문제에 나오는 식을 한번 보죠.

A * | R - C | + B * { N - ( R * C ) }

식을 두개로 나누어서 생각해볼게요.

아래 표처럼 두개로 나누면 두개의 식 모두 양수밖에 나오지 못하는걸 알 수 있습니다.

따라서 두개의 식의 최소값을 구해야 합니다.

A * | R - C |  >= 0    (첫번째 식)	B * { N - ( R * C ) }  >= 0    (두번째 식)
가장 최소값을 가지는 순간은 R = C 경우 입니다. 따라서 R = C의 경우(제곱)만 생각해봅니다.	가장 최소값을 가지는 순간은 N = R * C 경우 입니다.  따라서 N >= R * C의 경우만 생각해봅니다. R과 N/R이죠.

사실 이걸 몰라도 포문 계속 돌리면 풀수 있을것 같습니다.

대신 오버플로우 처리를 해줘야겠죠.

오버플로우는 Math와 try를 통해서 처리 했습니다.

오버플로우가 난 순간 부터 계산할 필요가 없기 때문에 break를 수행합니다.

다른 분이 짠 코드도 보고 학습하고 싶은데 코드 열람이 불가능하네요.(왜죠왜죠왜죠왜죠?)

이 문제를 통해 인내와 오버플로우 처리에 대해서 학습할 수 있었네요.

import java.util.Scanner; public class Solution { static int N, A, B; public static void main(String[] args) { Scanner sc = new Scanner(System.in); int num = sc.nextInt(); for ( int i = 1; i <= num; i++ ) { N = sc.nextInt(); A = sc.nextInt(); B = sc.nextInt(); int result = -1; for ( int j = (int) Math.sqrt(N); j > 1 ; j-- ) { //R = C일 경우 int temp = getResult(j, j); if ( temp < 0 ) { break; } result = getRealResult(result, temp); } for ( int j = (int) Math.sqrt(N); j > 1 ; j-- ) { //N >= R * C일 경우 int temp = getResult(N/j, j); if ( temp < 0 ) { break; } result = getRealResult(result, temp); } System.out.println("#" + i + " " + result); } } public static int getResult(int left, int right) { int minus = left - right; if ( minus < 0 ) { //절대값 속의 마이너스 계산 부분 minus *= -1; } try { //Math를 통해 overflow 찾아내기 int cal1 = Math.multiplyExact(A, minus); //첫번째 식 계산 값 int cal2 = Math.multiplyExact(left, right); //두번째 식 계산 값 cal2 = N - cal2; cal2 = Math.multiplyExact(B, cal2);         return Math.addExact(cal1, cal2); //overflow가 아니면 값 리턴     } catch (Exception e) { //overflow일 경우 -1 리턴         return -1;     } } public static int getRealResult(int result, int temp) { if ( result == -1 ) { return temp; } else { return result > temp ? temp : result; } } }