BOJ_7568_덩치

1.

구분: brute-force

언어: Java

전략

• 덩치를 비교할 2 사람을 고른다 - 조합을 이용
• 몸무게를 먼저 비교하고, 더 큰 사람이 키도 크다면, 작은 사람보다 큰 사람 수를 저장하는 배열(rank)에 1을 증가

 

---

2. 코드

import java.util.Arrays;
import java.util.Scanner;


public class Main {
	
	static int[] rank, result;
	
	static int n;
	static class Body{
		int height, weight; 
		public Body(int weight, int height) {
			this.height = height; 
			this.weight = weight;
		}
	}
	static Body[] body;
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		
		n = scanner.nextInt();
		
		body = new Body[n];
		for(int i = 0; i<n; i++) {
			body[i] = new Body(scanner.nextInt(), scanner.nextInt());
		}
        
        //나보다 큰 사람들의 수+1을 할 rank배열
		rank = new int[n];
		//2명의 조합을 만들 배열
        result = new int[2];
		Arrays.fill(rank, 1);
		comb(0,0);
		
		for(int i : rank) {
			System.out.print(i+" ");
		}
		

	}//main
	
    //2개씩 조합을 만들어서 비교를 한다
	private static void comb(int cnt, int start) {
    	//2명을 다 골랐을 경우
		if(cnt == 2) {
			//body[0]과 body[1]의 weight비교
			//0번이 더 크다면 - 키도커야함
			if(body[result[0]].weight>body[result[1]].weight) {
				if(body[result[0]].height>body[result[1]].height) {
					rank[result[1]]++;
				}
			}
			//1번이 더 크면
			else if(body[result[0]].weight<body[result[1]].weight) {
				if(body[result[0]].height<body[result[1]].height) {
					rank[result[0]]++;
				}
			}
			return;
		}
		for(int i = start; i<n; i++) {
			result[cnt] = i;
			comb(cnt+1, i);
		}
		
		
	}

}

---

3. 

• 기본적은 조합을 구하는 문제
• 덩치를 구할 수 없는 경우는 무시하자 
• 의문: 몸무게가 같은데 키가 더 큰 사람이 있다면? - 문제에서는 이 경우는 고려하지 않아도 풀린다