[백준] 7568번

문제출처: https://www.acmicpc.net/problem/7568

7568번: 덩치

 

브루트포스 알고리즘인데, 먼저 브루투 포스 알고리즘에 대해 간단히 이야기 하자면 이렇다.

주어진 경우의 모든 경우의 수를 구한다. 그리고 그 중에서 원하는 입력값에 맞는 값을 찾아낸다.

이러기 위해선 완전 탐색이라는 것을 해야 예외없이 완벽하게 수행할 수 있다.

​

브루트 포스는 선형 구조일 때는 순차 탐색을,

비선형 구조일 때는 깊이 우선 탐색(DFS), 너비 우선 탐색(BFS)을 도구로 사용한다.

그러나 엄연히 말하면 DFS는 백트래킹과 관련이 깊고 BFS가 브루트 포스와 관련이 깊다.

난 아직도 BFS 문제를 처음 접하고 먹은 충격을 잊을 수 없다.

까막눈인 채로 집단지성의 힘을 빌리기 위해 들어간 위키백과에서 눈을 뗄 수가 없었다.

 

https://ko.wikipedia.org/wiki/%EB%84%88%EB%B9%84_%EC%9A%B0%EC%84%A0_%ED%83%90%EC%83%89

너비 우선 탐색 - 위키백과, 우리 모두의 백과사전

 

사람들 정말 똑똑하구나를 코드 짜면서, 그리고 코드를 접하면서 항상 느낀다.

특히 깊이 우선 탐색과 너비 우선 탐색을 공부할때...

하기 싫어서 문제 유형을 요리조리 피해가며 쉬운 그리디나 수학연산 구현만 했더니 실력이 오르지 않는다.

당연하다. 풀고싶은 문제만 푸니 그렇다. ...다음주 기사시험 이후로는 BFS와 DFS를 제대로 공부해야겠다.

난 아직 하수다..

​

아무튼, 돌아와서 7568번 문제는 요약하면 다음과 같다.

문제에서 정의한 '덩치'의 크기는 키도, 몸무게도 모두 커야 더 큰 것으로 인정된다.

가령 A와 B의 키와 몸무게를 측정했을 때, A의 키가 더 큰데 몸무게는 B보다 작다면 그건 덩치 우위를 가릴 수 없다.

A의 키도 몸무게도 B보다 크다면 그건 A의 덩치가 큰 것이라고 정의한다.

두 가지의 입력값을 비교해야하기 때문에 2차원의 배열을 생성하고, 0번째와 1번째 파라미터를 비교해간다.

for i in range 반복문 내에 for j in range 반복문을 돌려주면 2차원 배열의 두 값을 완전탐색 할 수있다.

만일 그 두 값이 덩치가 더 큰 상대를 만나면 한 순위 뒤로 밀려난다.

그 다음 만난 값도 덩치가 더 큰 상대라면 또 한 순위 뒤로 밀려난다.

그렇게 한 바퀴 다 돌면 해당 학생의 순위가 정해진다.