[SWEA] 1491. 원재의 벽 꾸미기 D3 JAVA (자바) 풀이

문제 1491번 (브루트포스)

 

1 X 1타일 N개를 이용해 R X C 크기의 직사각형 인테리어 만들기

원재의 방은 정사각형 형태이기 때문에 만드는 직사각형 인테리어를 최대한 정사각형에 가깝게 만들면서 최대한 많은 타일을 사용해라

가중치 A, B를 가지고 나름의 식 = A X lR – Cl + B X (N - R X C)

위의 값을 최소화하라

 [입력]

 첫 번째 줄에 테스트 케이스의 수 T

 각 테스트 케이스의 첫 번째 줄에는 세 정수 N, A, B(1 ≤ N, A, B ≤ 105)

 [출력]

 각 테스트 케이스마다 ‘#x'를 출력하고, 답을 출력한다.

 

 

 [과정]

 

 탐색하자 → 브루트포스 / dfs → 조건이 있다 → 백트래킹

 

 

※ 최적의 조건 ※
 

• A X |R – C| + B X (N - R X C)
  
  
  • A, B, N은 이미 정해진 수 고로 바꿀 수 있는 수는 R과 C
    
  • 조건 1) R - C가 작을수록 좋다 !
     
    • C는 R과 같다고 설정하되 R*C가 N이하일 경우에만 C 증가
      
      
  • 조건 2) R X C 가 N에 가까울수록 좋다 !
    
    
    • R을 N에 제곱근을 넘지 않도록 설정

 

 

 [코드]

import java.util.*;
import java.io.*;

class Solution
{
	public static void main(String args[]) throws Exception
	{
		Scanner sc = new Scanner(System.in);
		int T;
		T=sc.nextInt();
        
		for(int t = 1; t <= T; t++)
		{
            long N = sc.nextLong();
            long A = sc.nextLong();
            long B = sc.nextLong();
            long min = Long.MAX_VALUE;

            for(long R = 1; R<=Math.sqrt(N); R++ ){
                for(long C =R; C*R<=N; C++){
                    long temp = A*Math.abs(R-C) + B*(N-(R*C));
                    if(temp < min) min = temp;
                }
            }
            System.out.println("#"+t+" "+min);
        }
	}
}

 

 

 [해설]
     

 :  for(int t = 1; t <= T; t++)
    {
            long N = sc.nextLong();  N입력 
            long A = sc.nextLong();  A입력
            long B = sc.nextLong();  B입력
            long min = Long.MAX_VALUE;  min값 초기화

            for(long R = 1; R<=Math.sqrt(N); R++ ){  제곱근까지만 for문 돌리기
                for(long C =R; C*R<=N; C++){  C를 R과 최대한 가깝게 반복
                    long temp = A*Math.abs(R-C) + B*(N-(R*C));  조건식
                    if(temp < min) min = temp;  조건식 중에 가장 작은 값 출력
                }
            }
            System.out.println("#"+t+" "+min);
        }
    }

 

  

 

 

 

 

이제 풀어보러 갈께요 :)

 

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV2b9AkKACkBBASw

SW Expert Academy

 

 

* 독학으로 익히는 코딩이라 틀린 것이 있을 수 있습니다. 오류가 있다면 댓글을 통해 알려주세요. 감사합니다. *