일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | ||
6 | 7 | 8 | 9 | 10 | 11 | 12 |
13 | 14 | 15 | 16 | 17 | 18 | 19 |
20 | 21 | 22 | 23 | 24 | 25 | 26 |
27 | 28 | 29 | 30 | 31 |
- 서머싯몸
- 2858번
- python
- 정렬알고리즘
- 11047번
- 민음사북클럽
- Anaconda
- Algorithm
- osaka
- insertion sort
- vscode
- Selction Sort
- 레스트리s20
- 기숙사 바닥
- 리솜포레스트
- 헤브나인스파
- Beakjoon
- 나이순정렬
- bubble sort
- 정대건
- 리솜리조트
- Baekjoon
- Sort Algorithm
- 경로 찾기
- 인생의베일
- 10814번
- 2025
- 동전0
- 민음사
- 11403번
- Today
- Total
JIyeon's life
[Baekjoon] 2309 일곱 난쟁이 본문
알고리즘 분류
브루트 포스
문제 - https://www.acmicpc.net/problem/2309
-문제-
왕비를 피해 일곱 난쟁이들과 함께 평화롭게 생활하고 있던 백설공주에게 위기가 찾아왔다. 일과를 마치고 돌아온 난쟁이가 일곱 명이 아닌 아홉 명이었던 것이다.
아홉 명의 난쟁이는 모두 자신이 "백설 공주와 일곱 난쟁이"의 주인공이라고 주장했다. 뛰어난 수학적 직관력을 가지고 있던 백설공주는, 다행스럽게도 일곱 난쟁이의 키의 합이 100이 됨을 기억해 냈다.
아홉 난쟁이의 키가 주어졌을 때, 백설공주를 도와 일곱 난쟁이를 찾는 프로그램을 작성하시오.
-해결방법-
일단 다 해보는 수 밖에 없다!! ->그래서 브루트 포스 알고리즘이다.
일단 vector에 삽입한 후 , (첫번째 키,두번째 키), (첫번째 키,세번째 키) ,(첫번째 키,네번째 키), ... 이런식으로 두 가지 경우를 생각하고 이 두개의 경우가 아닌 난쟁이키를 다 더한 후 만약 100일경우 for문 빠져 나오기.
만약 (두번째 키, 첫번째 키) 이렇게 경우의 수는 앞에서 (첫번째 키, 두번째 키)와 같은 경우이므로 생각하지 않아도 된다.
<소스코드>
#include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { vector<int> h; vector<int> nanjang; int temp; int check = 0; for (int i = 0; i < 9; i++) { cin >> temp; h.push_back(temp); //cout << h[i] << endl; } int i, j; for (i = 0; i < 9; i++) { for (j = i + 1; j < 9; j++) { int sum = 0; //printf("%d %d\n", i, j); for (int k = 0; k < 9; k++) { if (k != i && k != j) { sum += h[k]; } } if (sum == 100) { check = 1; break; } } if (check == 1) break; } //printf("\n%d %d\n", i,j); for (int k = 0; k < 9; k++) { if (k != i && k != j) { nanjang.push_back(h[k]); } } sort(nanjang.begin(), nanjang.end()); for (int i = 0; i < 7; i++) cout << nanjang[i] << endl; return 0; } |
'algorithm > baekjoon' 카테고리의 다른 글
[Baekjoon] 1475 방 번호 (0) | 2018.10.02 |
---|---|
[Baekjoon] 2644 촌수계산 (0) | 2018.10.01 |
[Baekjoon] 2178 미로 탐색 (0) | 2018.09.27 |
[Baekjoon] 9012 괄호 (0) | 2018.09.20 |
[Baekjoon] 11650 좌표 정렬하기 (0) | 2018.09.20 |