Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | |||||
3 | 4 | 5 | 6 | 7 | 8 | 9 |
10 | 11 | 12 | 13 | 14 | 15 | 16 |
17 | 18 | 19 | 20 | 21 | 22 | 23 |
24 | 25 | 26 | 27 | 28 | 29 | 30 |
Tags
- BuildConfig
- 2501
- 약수 구하기
- 스카이라인 쉬운거
- 지능형 기차2
- Parcelize
- 완전탐색
- 프로그래머스
- BFS
- 백준
- SWEA
- 백준 퇴사
- EditorInfo
- 조합
- imeOptions
- hilt
- Parcelable
- 순열
- Kotlin
- 자바
- 최단경로
- EditText
- 시뮬레이션
- 백준 14501
- 순수함수
- dfs
- val
- 오르막수
- java
- Android
Archives
- Today
- Total
안드 공부를 해볼까?
[Java] SWEA 장훈이의 높은 선반 본문
728x90
1. 문제분석
https://swexpertacademy.com/main/code/problem/problemDetail.do
문제가 이해가지 않았지만 예제풀이를 보고 해결했다.
장훈이가 너무 커서 물건을 쌓아올린 것을 직원들이 힘을 합쳐 꺼낼려고 한다.
직원들끼리 탑을 쌓아서 물건을 가져와야하고 물건과 탑의 차가 가장 적은 것을 구하면 된다.
필자는 조합으로 풀었다. 모든 조합의 경우의 수를 구하고 탑이 물건의 높이보다 크고 그 차가 가장 작은 값을 출력하면 된다.
2. 구현
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.StringTokenizer;
public class Main {
static int min = Integer.MAX_VALUE;
static int height;
static int answer = 0;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int tc = Integer.parseInt(br.readLine());
for (int c = 1; c <= tc; c++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int size = Integer.parseInt(st.nextToken());
height = Integer.parseInt(st.nextToken());
st = new StringTokenizer(br.readLine());
int[] arr = new int[size];
for (int i = 0; i < size; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
//모든 조합 탐색
for (int i = 1; i <= size; i++) {
comb(arr, new boolean[size], 0, size, i);
}
System.out.println("#" + c + " " + min);
min = Integer.MAX_VALUE;
}
}
static void comb(int[] arr, boolean[] visited, int start, int n, int r) {
if (r == 0) {
int sum = 0;
for (int i = 0; i < n; i++) {
if (visited[i]) {
sum += arr[i];
}
}
//직원들이 탑을 쌓은 값 = sum
if(sum >= height){
int result = sum - height;
min = Math.min(result, min);
}
return;
}
for (int i = start; i < n; i++) {
visited[i] = true;
comb(arr, visited, i + 1, n, r - 1);
visited[i] = false;
}
}
}
백트래킹으로 조합을 구했다. 조합만 구할 수 있으면 쉽게 해결 가능한 문제다.
3. 마무리
보자마자 조합인 것을 알고 적용했더니 30분만에 해결했다.
문제가 어렵진 않았는데 문제내용만 보고 해석하는게 오래걸렸다.
반응형
'알고리즘 > SWEA' 카테고리의 다른 글
[Java] SWEA 미생물 격리 (0) | 2022.11.19 |
---|---|
[Java] SWEA 수영대회 결승전 (1) | 2022.11.17 |
[Java] SWEA 보호 필름 (0) | 2022.11.17 |
[Java] SWEA 등산로 조성 (0) | 2022.11.15 |
[Java] SWEA 오! 나의 여신님 (0) | 2022.10.14 |
Comments