[9229] 한빈이와 Spot Mart in Java

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

SW Expert Academy

 

---

접근 방식

조합을 이용해서 2개의 과자를 선택했고

2개의 과자의 무게를 합한 값이 최대가 될때 answer에 계속 값을 넣어주는 방식으로

값을 갱신하여 원하는 값을 구함.

 

 

시행 착오

make 매개변수에 start라는 변수를 넣어줘야하는데

이 부분을 빼먹어서 270개의 테케중 203개만 맞았다...

그래서 다시 생각을 해보니

조합에서는 start 변수가 필요하다는 걸 기억해냈다.

 

맨날 순열, 조합 헷갈려해서 이번 기회에 정리를 해보려한다.

---

 

ex) {1, 2, 3}에서 2개씩 뽑아내는 경우의 수를 찾아보자

 

1. 순열 (순서를 정해서 나열한다 = 순서를 중요하게 생각한다. )

: (1,2,3) ≠ (3,1,2) → 배열에 들어있는 숫자가 똑같아도 배치 순서가 다르면 다른 수로 인식한다.

 

1 - 2, 1 - 3

2 - 1, 2 - 3

3 - 1, 3 - 2

 

---

2. 조합 (순서를 신경쓰지 않는다)

: (1,2,3) == (3,1,2) → 위 예시처럼 배열에 들어있는 숫자가 똑같고, 배치 순서가 다르더라도 같은 수로 인식한다.

 

1 - 2, 1 - 3

2 - 3

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Solution {
    static int[] array;
    static int answer;
    static int m;
    static int temp;
    public static void make(int cnt, int start) {
        if (cnt==2) {
            if (temp<=m) {                
                answer = answer>temp?answer:temp;
            }
            return;
        }
        for(int i=start; i<array.length; i++) {
            temp+=array[i];
            make(cnt+1,i+1);
            temp-=array[i];
        }
    }
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int T=Integer.parseInt(br.readLine());
        for (int t = 1; t <= T; t++) {
            answer=-1;
            temp=0;
            StringTokenizer st = new StringTokenizer(br.readLine());
            int n=Integer.parseInt(st.nextToken()); // 과자봉지 개수
            m=Integer.parseInt(st.nextToken()); // 최대무개 M
            array=new int[n]; // 과자봉지 무게
            st=new StringTokenizer(br.readLine());
            for (int i = 0; i < n; i++) {
                array[i]=Integer.parseInt(st.nextToken());
            }
            make(0,0);
            sb.append("#"+t+" "+answer+"\n");
        }
        System.out.print(sb);
    }
}