공부 146일차: 백준 2309번 일곱 난쟁이 자바 java

2309 일곱 난쟁이

https://www.acmicpc.net/problem/2309

2309번: 일곱 난쟁이

 

 

---

백준 2309번 문제 일곱 난쟁이

---

문제

---

 

 

 

---

과정 생각해보기

---

 

브루트 포스 문제다브루트 포스는 모든 경우의 수를 다 확인하는 유형

 

7명을 더했을 때 100이 되어야 하는 게 핵심

 

1) 0으로 바꾸기

그래서 생각한 방법은 2명을 0으로 바꾸고 더해보는 거였다

 

예제 입력에 주어진 숫자들로 예를 들어보면,

 

0	7	23	19	10	15	25	8	13
0	0	23	19	10	15	25	8	13
0	7	0	19	10	15	25	8	13
0	7	23	0	10	15	25	8	13
0	7	23	19	0	15	25	8	13
0	7	23	19	10	0	25	8	13
0	7	23	19	10	15	0	8	13
0	7	23	19	10	15	25	0	13
0	7	23	19	10	15	25	8	0

...

20	7	23	19	0	0	25	8	13
20	7	23	19	0	15	0	8	13
20	7	23	19	0	15	25	0	13
20	7	23	19	0	15	25	8	0

...

이런 식으로 구해보면 된다

 

 

2) 9명 총합에서 빼기

이런 식으로 앞에서 0으로 만들었던 과정을 빼는 과정으로 바꾸는 방법

 

 

 

 

---

정답 인정 코드

---

 

1) 내가 짠 코드 (비추)

import java.io.*;
import java.util.Arrays;
 
public class Main {
 
    static int[] dwarves;
    static int len;
    
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        dwarves = new int[9];
        len = dwarves.length;    // 9명으로 고정되어 있긴 하지만 코드의 유연성을 위해 변수로 선언하기
        
        for(int i = 0; i < len; i++) {
            dwarves[i] = Integer.parseInt(br.readLine());
        }
        
        
        int[] answer = sevenDwarves(dwarves);
        for(int i : answer) {
            System.out.println(i);
        }
        
    }
    
    public static int[] sevenDwarves(int[] dwarves) {
        len = dwarves.length;
        int[] arr = dwarves;
        int[] answer = new int[7];
        // 7보다 적은데도 합이 100이 될 수도 있음 -> count로 난쟁이의 수를 센다 
        int count = 0;
        int sum = 0;
        
        for(int i = 0; i < len-1; i++) {    
            //배열의 끝에 있는 수는 항상 아래 코드에 껴 있으므로 확인할 필요 없다
            // + (j = i+1이라서 len까지 하면 배열의 크기를 벗어남)
            int temp1 = dwarves[i];    // 기존값 저장
            dwarves[i] = 0;
            
            for(int j = i+1; j < len; j++) {
                int temp2 = dwarves[j];    // 기존값 저장
                dwarves[j] = 0;
                
                for(int k = 0; k < len; k++){
                    sum += dwarves[k];
                    
                    // 0이 아니다 == 본래 숫자를 가지고 있었다
                    if(dwarves[k] != 0) {
                        count++;    // 본래 숫자를 가지고 더해진 난쟁이의 수 세기
                    }
                }
                
                if(count == 7 && sum == 100) {
                    int idx = 0;
                    for(int k = 0; k < len; k++) {
                        if(dwarves[k] != 0) {
                            answer[idx] = dwarves[k];
                            idx++;
                        }
                    }
                }
                
                //초기화
                count = 0;
                sum = 0;    
                dwarves[j] = temp2;    // 다시 값 넣어주기
            }
            dwarves[i] = temp1;    // 다시 값 넣어주기
        }
        
        Arrays.sort(answer);    // 오름차순 정렬
        return answer;
    }
 
}
 

정답처리되었고, 124ms긴 하지만 메모리를 너무 많이 잡아먹는 듯하고,

다른 분들 풀이를 봐야 배우니까 많이 찾아보았다

(무엇보다 너무 복잡하다)

 

2)

import java.io.*;
import java.util.Arrays;
 
public class Main {
 
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int[] dwarves = new int[9];
        int len = dwarves.length;    // 9명으로 고정되어 있긴 하지만 코드의 유연성을 위해 변수로 선언하기
        int fake1 = 0;
        int fake2 = 0;
        int sum = 0;
        
        for(int i = 0; i < len; i++) {
            dwarves[i] = Integer.parseInt(br.readLine());
            sum += dwarves[i];
        }
        Arrays.sort(dwarves);
        
        for(int i = 0; i < len; i++) {
            for(int j = i+1; j < len; j++) {
                if(sum - dwarves[i] - dwarves[j] == 100) {
                    fake1 = dwarves[i];
                    fake2 = dwarves[j];
                }
            }
        }
        
        for(int i = 0; i < len; i++) {
            if(fake1 == dwarves[i] || fake2 == dwarves[i]) {
                continue;
            }
            System.out.println(dwarves[i]);
        }
    }
}
// 과정 https://gimbalja.tistory.com/281

 

나도 이런 방법으로 빼볼까 하다가 answer[] 배열의 크기를 넘어갈 거 같아서 말았는데

이렇게 바로 배열에서 출력하면 되는구나.. (왜 또다른 배열을 넣으려고 했지)처음에 총합을 구할 생각도 못했었다

 

 

 

---

다른 분들 풀이를 보니까 내 코드가 너무 부끄럽긴 하지만.. 이러면서 배우는 거라고 생각하기