[Baekjoon] 백준 일곱 난쟁이 (2309번)

백준 2309번 문제인 일곱 난쟁이에 대해 풀어보려 한다.

해당 문제의 링크는 아래에 첨부해 두겠다. 

(그리고 나는 내 주력 언어인 파이썬 으로 풀었다)

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

2309번: 일곱 난쟁이

 

문제는 아래와 같다.

 

 

 

 

✅ 문제

일곱 난쟁이 문제 (출처: 백준)

 

 

 

 

✅ 문제 풀이 접근 방법

처음에는 너무 오랜만에 코딩테스트 문제를 봐서 그런지 쉬운 문제임에도 불구하고 어떻게 접근해야 하는지 머릿속이 막막했다.

하지만 나는 적어가면서 수학적으로 접근을 해보았다.

아홉난쟁이 중 진짜 일곱 난쟁이를 찾아야 하는데 진짜 일곱 난쟁이의 키의 합이 100이라는 게 단서이다.

 

여기서 나는 아래와 같은 수식이 생각 났다.

"100 (일곱 난쟁이 키의 합) + x(가짜 두 난쟁이 키의 합) = 아홉 난쟁이 키의 합"

맞다 너무 당연한 것이다.  여기서 아홉 난쟁이의 키들은 주어지기 때문에 100(일곱 난쟁이 키의 합)을 우측항으로 넘기면 우리가 색출해야 하는 가짜 난쟁이 두 명의 키 합(x)이라는 단서를 알 수 있다.

 

 

 

 

✅ 문제 풀이

이제 본격적으로 문제를 풀어 보자

 

먼저 9명의 난쟁이들의 키를 입력받아야 한다. python에서는 input() 함수를 사용하면 입력을 받을 수 있다.

그럼 9개의 변수를 생성해서 input()를 해줘야 하는가? 그건 너무 비효율 적이다. 그래서 나는 for 문을 사용해서 아래와 같이 배열에 담아줬다. 난쟁이의 키를 담을 배열명은 dwarfs로 만들었다. 그리고 키는 자연수이기에 int로 변환해주었다.

 

sum() 함수를 사용해 입력받은 아홉 난쟁이의 키를 합해서 dwarf_sum이라는 변수에 저장해주었다.

 

dwarfs = []
for i in range(9):
    dwarfs.append(int(input()))
    
dwarf_sum = sum(dwarfs)

 

 

여기까지 해서 9명 각각 난쟁이의 키를 알게 되었고, 아홉 난쟁이의 키 총합까지 알게 되었다.

 

이제 가짜 난쟁이를 찾아낼 차례다.

우리가 가진 정보중 하나인 9 난쟁이의 각각의 키를 보유한 배열이다. 여기서 제일 처음 내가 생각한 그 수식을 통해 가짜난쟁이를 찾고 그 둘을 배열에서 제외해 줘 7 난쟁이를 출력해주면 된다.

 

배열 각각의 값들을 하나씩 확인하면서 두 난쟁이를 찾으려고 하면 2중 for문을 사용해야 한다. 내부에 바로 아까 수식의 조건으로 가짜 난쟁이들을 걸러내면 된다.

 

"아홉 난쟁이 키의 합(dwarf_sum) -  두 난쟁이의 키의 합 = 100"을 코드로 구현하면 아래와 같다.

if dwarf_sum - dwarfs[i] - dwarfs[j] == 100:

 

 

그리고 remove() 함수를 사용해서 가짜 난쟁이를 걸러주고 마지막으로 오름차순 정렬이니 sort() 함수를 사용하여 출력하면 된다. 

 

최종 코드는 아래와 같다.

 

 

 

 

✅ 최종 코드

 

for i in range(8):
    for j in range(i+1, 9):
        if dwarf_sum - dwarfs[i] - dwarfs[j] == 100:
            fake_dwarfs = [dwarfs[i], dwarfs[j]]
            dwarfs.remove(fake_dwarfs[0])
            dwarfs.remove(fake_dwarfs[1])
            dwarfs.sort()
            for dwarf in dwarfs:
                print(dwarf)
            break
    if len(dwarfs) == 7:
        break