[백준] S2 18442 우체국 1 (java)

www.acmicpc.net/problem/18442

18442번: 우체국 1

 

풀이

 

1) 조합으로 배열을 뽑는다

2) 각마을에서 뽑은배열중 가장 짧은 거리를 구해 더한다

2-1) 가장 짧은 거리는 오른쪽으로 갈때와 왼쪽으로 갈때의 거리중 최소이다.

3) 최솟값 갱신 + 결과 배열 저장

4) 최솟값과 결과배열 출력

 

주의사항

 

1) 가장 짧은 거리를 구할때 신경써야함

 

package com.baekJoon;

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

public class BJ_S2_18442_우체국1 { 
	static BufferedReader input = new BufferedReader(new InputStreamReader(System.in)); 
	static StringTokenizer tokens; 
	static int V, P;
	static long L, village[], post[], result[], answer[], minSum = Long.MAX_VALUE;
	public static void main(String[] args) throws NumberFormatException, IOException { 
		input = new BufferedReader(new StringReader(src)); 
		tokens = new StringTokenizer(input.readLine()); 
		V = Integer.parseInt(tokens.nextToken()); 
		P = Integer.parseInt(tokens.nextToken()); 
		L = Long.parseLong(tokens.nextToken());
		village = new long[V];
		post = new long[P];
		result = new long[P];
		answer = new long[P];
		
		tokens = new StringTokenizer(input.readLine()); 
		for(int v=0; v<V; v++) {
			village[v] = Long.parseLong(tokens.nextToken());
		}
		
		combi(0,0);
		
		System.out.println(minSum);
		for(long x : answer) {
			System.out.print(x+" ");
		}
			
	}
	private static void combi(int start, int cnt) {
		if(cnt == P) {
			getDist();
			return;
		}
		for(int i=start; i<V; i++) {
			result[cnt] = village[i];
			combi(i+1, cnt+1);
		}
	}
	private static void getDist() {
		long sumDist = 0;
		for(int v=0; v<V; v++) {
			long minDist = Long.MAX_VALUE;
			for(int p=0; p<P; p++) {
				long chai = Math.min(Math.abs(village[v] - result[p])
						, Math.min(village[v], result[p])+L - Math.max(village[v], result[p]));
				if(minDist > chai) {
					minDist = chai;
				}
			}
			sumDist += minDist;
		}
		
		if (sumDist < minSum) {
			minSum = sumDist;
			answer = result.clone();
		}
	}
	static String src = // 예제 입력
			"10 5 200\r\n" + 
			"1 2 3 6 7 9 11 22 44 50";
}

 

 

후기

 

요즘 내가 예전에 못풀었던 문제를 풀고있다.

풀면서 느끼지만 불과 2달 정도 밖에 안되었는데 왜 이런것도 못풀고 빌빌거렸나 한심할 따름이다.

그래도 성장한 모습을 보니 기분이 좋다.