[Algorithm Study] D3_5215 햄버거 다이어트
SW Expert Academy
SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!
swexpertacademy.com
IM 시험이 월요일에 끝나고 다시 알고리즘 스터디를 시작하면서 하루에 한 문제씩 맡아서 발표를 하기로 했다. IM 시험에 대해서도 할 말이 많은데 이건 언제 따로 정리하지... 아무튼 SW가 어제 스터디 회의에서 자기가 리스트업 한 문제파일을 공유해주었고, 한사람이 하루에 한 문제씩, 총 네문제를 소화하고 가자 라는 야심찬 목표를 가지고 오늘부터 스터디가 진행되게 되었다. 문제들은 거의 수업시간에 다룬 문제들로 SWEA D3,4 수준 정도로 분포되어 있었고 BOJ는 내가 레벨을 잘 알지는 못하지만 내가 쉽게 풀지 못하는 정도의 난이도가 분명해 보였다.
스터디 문제를 배부 받으면서 스스로 바랬던 것은, 되도록이면 구글에서 솔루션을 찾지 않고 싶다는 것이었는데, 이 문제를! D3문제를 처음으로! 내 힘으로 풀게 되었다! 아침에 코드를 작성했는데 이클립스에서는 돌아가는데 SWEA에서는 테케 20개 중 8개만 맞고 나머지가 다 틀렸다고 떠서 내심 실망하다가 방금 카페 와서 조금 수정해보았더니 SWEA에서도 PASS가 떴다! 막연하게 순조부는 너무 어려워! 라고 생각하고, D3는 내가 못풀어! 라고 생각했는데, 조금씩 아주 미세하지만 성장하는 느낌이 들어서 다행이기도 하고 기분도 너무 좋았다. 아침부터 바디프로필 문제로 엄마랑 언성을 높였는데, 그 서러움이 한번에 사라지는 느낌이였다!
먼저 코드는 SWEA_5215 랑 SWEA_5215_clean 버전이 있는데 애착이 더 가는 코드는 SWEA_5215 인데, 테스트출력도 덕지덕지 붙여보고 이리저리 코드도 옮겨보고 수정해본 손떼묻은 일기장을 넘겨보는 느낌이다 ♥
아침에 테스트케이스 오류가 떴던 이유는 max초기화 시점이 잘못되었기 때문인 것 같다. 원래는 static int max 를 선언하면서 Integer.MIN_VALUE로 초기화까지 같이 해주었는데, 예를들어 테스트케이스 8까지의 max값보다 테스트케이스 9의 max값이 더 작아버리면 잘못된 결과가 출력되겠구나 하는 생각이 들었다. 그래서 테스트케이스별로 프로그램을 실행하는 경우, SubSet()함수를 호출하기 전에 max값을 초기화 해주었다. 그랬더니 SWEA에서 테스트케이스가 모두 통과되었다. 오예!
+ 두시간 정도동안 Subset 함수 아래부분 재귀호출을 어떻게든 이해해 보고자 노력했지만 물거품이 되었다. 지금은 Subset, Permutation, Combination 다 잘 이해하지 못하고 그냥 외워서 쓰고 있는거라서 반쪽짜리 맞은 것 같은 느낌에 이해하고 싶었는데 잘 안되서 속상하다. 이해 안되면 계속계속 보라는데, 언제까지 보면 이해할 수 있을까! 이번주까지는 스터디에서 계속 순조부를 할 것 같으니까 더 공부해야 할 것 같다. 웹 프론트엔드는 또 언제하지?
package s0901;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
// 햄버거 다이어트
public class SWEA_5215 {
static int N; // 재료 수 (NUMBER)
static int L; // 제한 칼로리 (LIMIT)
static int[] T; // 각 재료별 맛 점수 (TASTE)
static int[] K; // 각 재료별 칼로리 (C(K)ALORIE)
static boolean[] isSelected;
static int sumK, sumT;
static int max;
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
StringTokenizer st = null;
int TC = Integer.parseInt(br.readLine().trim());
for (int tc = 1; tc <= TC; tc++) {
sb.append("#").append(tc).append(" ");
st = new StringTokenizer(br.readLine().trim(), " ");
N = Integer.parseInt(st.nextToken()); // 재료 수 받아옴
L = Integer.parseInt(st.nextToken()); // 제한 칼로리 받아옴
T = new int[N]; // 각 재료별 맛 점수를 저장하는 배열 선언
K = new int[N]; // 각 재료별 칼로리를 저장하는 배열 선언
isSelected = new boolean[N]; // SubSet 함수에서 원소 선택여부를 알기 위해 사용하는 불리언 배열 선언
max = Integer.MIN_VALUE; // SubSet 함수에서 맛의 합의 최대값을 저장하기 위한 변수 선언
for (int n = 0; n < N; n++) {
st = new StringTokenizer(br.readLine().trim(), " ");
T[n] = Integer.parseInt(st.nextToken());
K[n] = Integer.parseInt(st.nextToken());
}
//System.out.println(Arrays.toString(T));
//System.out.println(Arrays.toString(K));
// 구현 해야 할 로직 :
// 민기가 좋아하는 햄버거를 먹으면서도 다이어트에 서공할 수 있도록 정해진 칼로리 이하의 조합 중 민기가 가장 선호하는 햄버거를 조합해 주는 로직
// 정해진 칼로리 이하의 조합 = 칼로리 배열에 담은 원소들을 가지고 재귀 탈출 조건에 추가해 준다
// 민기가 가장 선호하는 햄버거 = 칼로리 배열에 담긴 원소들의 조합 중 그 합이 최대가 되는 경우를 생각해 준다
SubSet(0);
// Combination 이 아니라 SubSet 인 이유 :
// Combination 이어야 한다면 nCr 이기 때문에 n 뿐 만 아니라 r에 대한 정보도 나와야 한다 (몇개를 뽑아야 하는지에 대한 정보)
// 하지만 r에대한 정보가 나오지 않있기 때문에, 뽑는 수의 제한 없이 모든 경우의 수를 따져주는 SubSet (부분집합)을 사용해 주어야 한다
// 고 생각햇는데 Combination을 사용해서 풀이한 솔루션 발견...
// https://data-make.tistory.com/494 (Combination)
// https://sohee-dev.tistory.com/18 (SubSet)
sb.append(max).append("\n");
}
System.out.println(sb.toString());
}
private static void SubSet(int cnt) {
if (cnt == N) { // 부분집합을 다 만들었을 때,
sumK = 0;
sumT = 0;
System.out.println("맛 부분집합 출력 : ");
for (int i = 0; i < isSelected.length; i++) {
System.out.print((isSelected[i]?T[i]:"X") + " ");
}
System.out.println();
System.out.println("칼로리 부분집합 출력 : ");
for (int i = 0; i < isSelected.length; i++) {
System.out.print((isSelected[i]?K[i]:"X") + " ");
if (isSelected[i]) { // 뽑힌 원소들 중에서,
sumT = sumT + T[i];
sumK = sumK + K[i];
if (sumK < L) { // 재료별 칼로리의 합이 제한칼로리를 넘지 않을 때,
if (max < sumT) { // 칼로리의 합이 max 값보다 크다면,
max = sumT; // max 값에 sumT를 저장해준다
}
}
}
}
System.out.println();
System.out.println("맛의 합 : " + sumT);
System.out.println("칼로리의 합 : " + sumK);
System.out.println("답 : " + max);
System.out.println();
return;
}
isSelected[cnt] = false;
SubSet(cnt+1);
isSelected[cnt] = true;
SubSet(cnt+1);
}
}
package s0901;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
// 햄버거 다이어트
public class SWEA_5215_clean {
static int N;
static int L;
static int[] T;
static int[] K;
static boolean[] isSelected;
static int sumK, sumT;
static int max;
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
StringTokenizer st = null;
int TC = Integer.parseInt(br.readLine().trim());
for (int tc = 1; tc <= TC; tc++) {
sb.append("#").append(tc).append(" ");
st = new StringTokenizer(br.readLine().trim(), " ");
N = Integer.parseInt(st.nextToken());
L = Integer.parseInt(st.nextToken());
T = new int[N];
K = new int[N];
isSelected = new boolean[N];
for (int n = 0; n < N; n++) {
st = new StringTokenizer(br.readLine().trim(), " ");
T[n] = Integer.parseInt(st.nextToken());
K[n] = Integer.parseInt(st.nextToken());
}
max = Integer.MIN_VALUE;
SubSet(0);
sb.append(max).append("\n");
}
System.out.println(sb.toString());
}
private static void SubSet(int cnt) {
if (cnt == N) {
sumK = 0;
sumT = 0;
for (int i = 0; i < isSelected.length; i++) {
if (isSelected[i]) {
sumT = sumT + T[i];
sumK = sumK + K[i];
if (sumK < L) {
if (max < sumT) {
max = sumT;
}
}
}
}
return;
}
isSelected[cnt] = false;
SubSet(cnt+1);
isSelected[cnt] = true;
SubSet(cnt+1);
}
}
