변경이력

돌아가기
4 277개 문자 추가

2016/11/24 04:03

wowpapa

트럭마다 다리에 들어오는 시간과 나가는 시간을 계산합니다.<br> 한 트럭이 다리에 들어오는 시간은<br> (자기포함 앞쪽의 트럭의 무게를 합산해나가다가 하중을 넘치는 트럭의 나가는 시간) 과<br> (내 직전 트럭의 다리에 들어오는 시간 + 1 ) 중<br> 큰 값이 됩니다.<br> 트럭이 다리에서 나가는 시간은 (들어오는 시간 + 다리의 길이) 입니다.<br> 입력받으면서 순차 계산하고 맨 마지막 트럭의 나가는 시간이 답이 됩니다.<br><br> 최악의 경우 O(NlogN) 으로 풀리며, 최선의 케이스는 O(N) 으로 해결됩니다.<br><br> ex) 입력이 다음과 같을 경우<br> 4 2 10<br> 7 4 5 6<br> List배열은 아래와 같이 채워집니다.<br> 7 1 3<br> 4 3 5 (무게가 넘치는 트럭의 나가는 시간 3, 직전 트럭의 들어가는 시간+1 은 2) -> 3 <br> 5 4 6 (무게가 넘치는 트럭의 나가는 시간 3, 직전 트럭의 들어가는 시간+1 은 4) -> 4 <br> 6 6 8 (무게가 넘치는 트럭의 나가는 시간 6, 직전 트럭의 들어가는 시간+1 은 5) -> 6 <br> ```{.java} import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; class A39TruckBridge { static StringTokenizer st; static int N; //트럭갯수 static int L; //다리길이 static int W; //최대하중 static int [][] List; static int sumWeight; static int lastTime; public static void main(String args[]) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); st = new StringTokenizer (br.readLine()); N = Integer.parseInt(st.nextToken()); L = Integer.parseInt(st.nextToken()); W = Integer.parseInt(st.nextToken()); List = new int [N][3]; // 0컬럼은 트럭무게, 1컬럼은 다리에 들어서는 시간, 2컬럼은 다리를 빠져나가는 시간 // 첫번째 트럭의 값을 입력 st = new StringTokenizer (br.readLine()); List[0][0] = Integer.parseInt(st.nextToken()); List[0][1] = 1; List[0][2] = List[0][1] + L; for (int i=1; i<N; i++) { List[i][0] = Integer.parseInt(st.nextToken()); sumWeight = List[i][0]; for (int x = i-1; x >= 0; x--) { sumWeight += List[x][0]; lastTime = List[x][2]; if (sumWeight > W) break; } List[i][1] = Math.max(List[i-1][1]+1, lastTime); List[i][2] = List[i][1] + L; } System.out.println(List[N-1][2]); } } ```
트럭마다 다리에 들어오는 시간과 나가는 시간을 계산합니다.<br> 한 트럭이 다리에 들어오는 시간은<br> (자기포함 앞쪽의 트럭의 무게를 합산해나가다가 하중을 넘치는 트럭의 나가는 시간) 과<br> (내 직전 트럭의 다리에 들어오는 시간 + 1 ) 중<br> 큰 값이 됩니다.<br> 트럭이 다리에서 나가는 시간은 (들어오는 시간 + 다리의 길이) 입니다.<br> 입력받으면서 순차 계산하고 맨 마지막 트럭의 나가는 시간이 답이 됩니다.<br><br> 최악의 경우 O(NlogN) 으로 풀리며, 최선의 케이스는 O(N) 으로 해결됩니다.<br><br> ex) 입력이 다음과 같을 경우<br> 4 2 10<br> 7 4 5 6<br> List배열은 아래와 같이 채워집니다.<br> 7 1 3<br> 4 3 5 (무게가 넘치는 트럭의 나가는 시간 3, 직전 트럭의 들어가는 시간+1 은 2) -> 3 <br> 5 4 6 (무게가 넘치는 트럭의 나가는 시간 3, 직전 트럭의 들어가는 시간+1 은 4) -> 4 <br> 6 6 8 (무게가 넘치는 트럭의 나가는 시간 6, 직전 트럭의 들어가는 시간+1 은 5) -> 6 <br> ```{.java} import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; class A39TruckBridge { static StringTokenizer st; static int N; //트럭갯수 static int L; //다리길이 static int W; //최대하중 static int [][] List; static int sumWeight; static int lastTime; public static void main(String args[]) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); st = new StringTokenizer (br.readLine()); N = Integer.parseInt(st.nextToken()); L = Integer.parseInt(st.nextToken()); W = Integer.parseInt(st.nextToken()); List = new int [N][3]; // 0컬럼은 트럭무게, 1컬럼은 다리에 들어서는 시간, 2컬럼은 다리를 빠져나가는 시간 // 첫번째 트럭의 값을 입력 st = new StringTokenizer (br.readLine()); List[0][0] = Integer.parseInt(st.nextToken()); List[0][1] = 1; List[0][2] = List[0][1] + L; for (int i=1; i<N; i++) { List[i][0] = Integer.parseInt(st.nextToken()); sumWeight = List[i][0]; for (int x = i-1; x >= 0; x--) { sumWeight += List[x][0]; lastTime = List[x][2]; if (sumWeight > W) break; } List[i][1] = Math.max(List[i-1][1]+1, lastTime); List[i][2] = List[i][1] + L; } System.out.println(List[N-1][2]); } } ```
3 126개 문자 추가

2016/11/24 03:56

wowpapa

2 8개 문자 추가

2016/11/24 03:54

wowpapa

1 Original

2016/11/24 03:20

wowpapa

코딩도장

코딩도장은 프로그래밍 문제풀이를 통해서 코딩 실력을 수련(Practice)하는 곳입니다.