백준 14244: 트리 만들기(java)

문제

---

풀이

 

정점 0의 레벨을 1이라 하자. 정점 0은 무조건 정점 1과만 연결된 리프여야 하고, 최하위 (m-1)개의 정점들은 모두 바로 위 정점과 연결된 리프이므로 레벨 (n-m-1)까지의 정점들은 바로 다음 정점과만 연결된다.

트리 예시

for문을 사용해 위 내용을 그대로 구현하면 된다.

 

위 방식으로 풀었을 때 예제 4가 예시 출력과 다르게 출력됐는데, 정답으로 채점되기는 한다.

 

전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws IOException{
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st=new StringTokenizer(br.readLine());
		int n=Integer.parseInt(st.nextToken());
		int m=Integer.parseInt(st.nextToken());
		
		StringBuilder sb=new StringBuilder();
		
		for(int i=0; i<n-m; i++) {	//정점 (n-m-1)까지 바로 다음 정점과 연결
			sb.append(i+" "+(i+1)+"\n");
		}
		
		int upperleaf=n-m;	//upperleaf=최하위 리프들 바로 위의 정점
		for(int i=1; i<m; i++) {
				sb.append(upperleaf+" "+(upperleaf+i)+"\n");
                //upperleaf 정점은 (m-1)개의 리프들을 자식으로 가짐 
		}
		
		System.out.println(sb);
	}
}