[Python, C] 백준 온라인 저지 2309번

브론즈 LV2 https://www.acmicpc.net/problem/2309

2309번: 일곱 난쟁이

 

왕비를 피해 일곱 난쟁이들과 함께 평화롭게 생활하고 있던 백설공주에게 위기가 찾아왔다. 일과를 마치고 돌아온 난쟁이가 일곱 명이 아닌 아홉 명이었던 것이다.

아홉 명의 난쟁이는 모두 자신이 "백설 공주와 일곱 난쟁이"의 주인공이라고 주장했다. 뛰어난 수학적 직관력을 가지고 있던 백설공주는, 다행스럽게도 일곱 난쟁이의 키의 합이 100이 됨을 기억해 냈다.

아홉 난쟁이의 키가 주어졌을 때, 백설공주를 도와 일곱 난쟁이를 찾는 프로그램을 작성하시오.

 

 

 

[Python]

 

풀이 방법:

 

다른 사람들 코드를 찾아보며 알게 되었는데 [브루트포스]* 와 [정렬] 을 이용한 문제였다.

 

* 브루트포스 : 모든 경우의 수를 탐색하면서 요구조건에 충족되는 결과만을 가져온다 (노가다)

 

    문제 해결 방법
      1. 주어진 문제를 선형 구조로 구조화 한다.
      2. 구조화된 문제공간을 적절한 방법으로 해를 구성할 때까지 탐색한다.
      3. 구성된 해를 정리한다.

 

 

아홉 난쟁이의 키를 리스트 형태로 저장한다. 

2 번 코드로 사용하는 방법을 연습 해야겠다.

# 코드 1
arr = []
for i in range(9):
    arr.append(int(input()))

# 코드 2 
arr = [int(input()) for i in range(9)]

 

그리고 임시 리스트를 만들어 만약 두 난쟁이의 키가 같을 경우 리스트를 초기화 한다.

if i == j:
	continue
temp = [] #초기화

 

키가 모두 다른 경우, 임시 리스트에 나열, 

임시 리스트의 원소 합이 100일 경우 break 후 정렬한다. (이 부분이 어려웠다)

for p in range(9):
            if p != i and p != j:
                temp.append(arr[p])
        if sum(temp) == 100:
            break

 

 

 

정답:

arr = []
for i in range(9):
    arr.append(int(input()))

temp = []
for i in range(9):
    for j in range(9):
        
        if i == j:
            continue
        temp = [] #초기화
        
        for p in range(9):
            if p != i and p != j:
                temp.append(arr[p])
        if sum(temp) == 100:
            break
    if sum(temp) == 100:
        break

temp.sort() # 정렬

for j in temp:
    print(j)

 

 

 

[C]

 

풀이 방법:

 

C언어가 난이도가 훨씬 있는 것 같다.

 

해당 부분이 어려웠다. 

    // 찐 난쟁이의 키가 아닌 두 수 찾기
	int p = 0;
	int q = 0;
	// 이중 for문 이용
	for (i = 0; i < 9; i++) {
		for (j = i + 1; j < 9; j++) { // j = i + 1 인 이유
			if ((dwarf[i] + dwarf[j]) == over) {
				p = i;
				q = j;
				break;
			}
		}
	}

 

정답:

 

#include <stdio.h>

int main() {
	int dwarf[9]; //난쟁이의 키를 담을 배열
	int total = 0; //제시된 키의 전체합 
	int over = 0; //초과한 양
	int i, j; 

	for ( i = 0; i < 9; i++) { //입력받는 부분
		scanf("%d", &dwarf[i]);
		total = total + dwarf[i];
	}

	over = total - 100; // 100 초과 수 확인
	
	// 찐 난쟁이의 키가 아닌 두 수 찾기
	int p = 0;
	int q = 0;
	// 이중 for문 이용
	for (i = 0; i < 9; i++) {
		for (j = i + 1; j < 9; j++) {
			if ((dwarf[i] + dwarf[j]) == over) {
				p = i;
				q = j;
				break;
			}
		}
	}


	int tmp;
	int r_dwarf[7]; //찐 난쟁이 키의 리스트
	j = 0;
	for (i = 0; i < 9; i++) {
		if (i != p && i != q) {
			r_dwarf[j] = dwarf[i];
			j++;
		}
	}

	// 찐 난쟁이 키 리스트 정렬
	for (i = 0; i < 7; i++) {
		for (j = i + 1; j < 7; j++) {
			if (r_dwarf[i] > r_dwarf[j]) {
				tmp = r_dwarf[i];
				r_dwarf[i] = r_dwarf[j];
				r_dwarf[j] = tmp;
			}
		}
	}

	//오름차순으로 출력
	for (i = 0; i < 7; i++) {
		printf("%d\n", r_dwarf[i]);
	}
}