문제 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 증가
- C는 R과 같다고 설정하되 R*C가 N이하일 경우에만 C 증가
- 조건 2) R X C 가 N에 가까울수록 좋다 !
- R을 N에 제곱근을 넘지 않도록 설정
- A, B, N은 이미 정해진 수 고로 바꿀 수 있는 수는 R과 C
[코드]
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
SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!
swexpertacademy.com
* 독학으로 익히는 코딩이라 틀린 것이 있을 수 있습니다. 오류가 있다면 댓글을 통해 알려주세요. 감사합니다. *
'SWEA' 카테고리의 다른 글
[SWEA] 13038. 교환학생 D3 JAVA (자바) 풀이 (0) | 2024.05.12 |
---|---|
[SWEA] 1206. [S/W 문제해결 기본] 1일차 - View D3 JAVA (자바) 풀이 (0) | 2024.05.12 |
[SWEA] 3307. 최장 증가 부분 수열 D3 JAVA (자바) 풀이 (1) | 2024.05.07 |
[SWEA] 1244. [S/W 문제해결 응용] 2일차 - 최대 상금 D3 JAVA (자바) 풀이 (0) | 2024.05.06 |