[Baekjoon] 1756_피자 굽기

Gold V

문제(출처: https://www.acmicpc.net/problem/1756)

---

< 피자 굽기>

 

문제 풀이

 

먼저 오븐의 지름을 위에서부터 들어갈 수 있는 지름으로 바꿔주는 것이 중요한 부분이었다.

바꿔준 후 밑에서부터 피자를 넣어주며 위치를 찾거나 이분 탐색으로 문제를 해결하는 방법이 있었지만, 

난 밑에서부터 피자를 넣어주는 방법을 택하였다.

 

- 시간 초과 코드 (Java)

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 bf=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=new StringTokenizer(bf.readLine());
		
		// 오븐의 깊이, 피자 반죽의 개수
		int D=Integer.parseInt(st.nextToken());
		int N=Integer.parseInt(st.nextToken());
		
		// 오븐의 지름
		int arr[]=new int[D];
		st=new StringTokenizer(bf.readLine());
		for(int i=0; i<D; i++) {
			arr[i]=Integer.parseInt(st.nextToken());
		}
		
		// 피자 반죽의 지름
		int pizza[]=new int[N];
		st=new StringTokenizer(bf.readLine());
		for(int i=0; i<N; i++) {
			pizza[i]=Integer.parseInt(st.nextToken());
		}
		
		boolean flag=false;
		boolean visited[]=new boolean[D];
		int cnt=0;
		
		for(int i=0; i<N; i++) {
			if(flag) break;
			for(int j=0; j<D; j++) {
				if(!visited[j]) {
					if(pizza[i]>arr[j]) {
						if(j==0) {
							flag=true;
							break;
						}
						visited[j-1]=true;
						cnt+=1;
						break;
					}
				}else {
					if(j==0) {
						flag=true;
						break;
					}
					if(!visited[j-1] && pizza[i]<=arr[j-1]) {
						visited[j-1]=true;
						cnt+=1;
						break;
					}
					
				}
			}
		}
		if(cnt!=N) System.out.println(0);
		else {
			for(int i=0; i<D; i++) {
				if(visited[i]) {
					System.out.println(i+1);
					break;
				}
			}
		}
	}
}

이렇게 다 완탐하니까 시간초과 날 수밖에.. ^^

 

 - my solution (Java)

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

public class _1756_ {

	public static void main(String[] args) throws IOException {
		BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=new StringTokenizer(bf.readLine());
		
		// 오븐의 깊이, 피자 반죽의 개수
		int D=Integer.parseInt(st.nextToken());
		int N=Integer.parseInt(st.nextToken());
		
		// 오븐의 지름
		int arr[]=new int[D];
		st=new StringTokenizer(bf.readLine());
		for(int i=0; i<D; i++) {
			arr[i]=Integer.parseInt(st.nextToken());
			if(i>0) {
				if(arr[i-1]<arr[i]) arr[i]=arr[i-1];
			}
		}
		
		// 피자 반죽의 지름
		int pizza[]=new int[N];
		st=new StringTokenizer(bf.readLine());
		for(int i=0; i<N; i++) {
			pizza[i]=Integer.parseInt(st.nextToken());
		}
		
		boolean visited[]=new boolean[D];
		int j=D-1, cnt=0, result=0;
		
		for(int i=0; i<N; i++) {
			while(j>=0) {
				if(arr[j]>=pizza[i]) {
					visited[j]=true;
					result=j+1;
					cnt+=1;
					j-=1;
					break;
				}
				j-=1;
			}
		}
		if(cnt!=N) System.out.println(0);
		else System.out.println(result);
	}
}

 

Main

- 오븐의 깊이(D), 피자 반죽의 개수(N) 입력

- 오븐의 지름 입력과 동시에 지름 길이 맞춰줌

- 피자 반죽의 지름 입력

- 오븐 밑에서부터 탐색하며 피자의 지름보다 크거나 같은 곳에 피자 반죽을 넣어줌.

- 피자 반죽을 다 넣지 못하면 0 출력, 다 넣었다면 마지막 피자 반죽의 위치를 출력

 

❓ 여기서 '오븐의 지름 입력과 동시에 지름 길이 맞춰줌'이 무슨 뜻인가?

= 만약에 오븐의 지름이 5 6 7과 같이 주어졌다고 가정해 보자. 위에서부터 피자 반죽이 들어오면

아무리 밑에 오븐의 지름이 크다해도 5보다 큰 피자 반죽은 들어가지 못할 것이다. 

그러므로 5 6 7 -> 5 5 5로 바꿔주는 작업을 해주는 것이다.

---

생각🤔

 

처음에 다 탐색해서 시간초과가 발생했었다... 몰라서 친구한테 설명 들었던 문제..

 

 

---