[백준] 19941 햄버거 분배 - 그리디(탐욕법, Greedy) JAVA

https://www.acmicpc.net/problem/19941

19941번: 햄버거 분배

코드설명

기본적인 구현 문제 + 그리디 입니다. 

 

처음에는 동적계획법을 활용하여 해결하려했습니다. 

하지만, 이전에 어떤 햄버거를 선택하였는지, 그리고 모든 경우를 탐색하다 보니 시간초과가 발생했습니다.

시간초과를 피하기 위해 메모이제이션도 적용했지만, 이전에 어떤 햄버거를 선택하였는지를 저장(즉, 과거의 선택이 현재의 선택에 영향을 준다) 해야 했기에 메모이제이션을 적용해도 메모리초과가 발생합니다.

 

두번째 방법은, 누적합을 활용하여 해당 구간에 존재하는 햄버거의 개수를 모두 센뒤, 일종의 슬라이딩 윈도우로 칸을 이동해가며 햄버거의 개수가 존재할경우 하나씩 먹으면서 처리하려고 했습니다. 하지만 이 방식의 슬라이딩 윈도우는 어떤 햄버거를 선택했는지는 알 수 없으므로 사용할 수 없었습니다.

 

세번째는, 그리디 알고리즘으로, 항상 사람은 식탁의 맨 앞에 있는 먹을 수 있는 햄버거부터 먹는다면 모든 사람들이 최대로 먹을 수 있음을 활용합니다. 이는 먹는 방법을 반드시 앞에서 먹도록 순서를 강제합니다.즉, 가장 앞에있는 햄버거부터 먹어야 뒤에 있는 사람들이 햄버거를 먹을 수 있습니다.

 

구현하면서,  아래와 같이 -K 부터 K까지를 반복문으로 표현하고 (해당 K를 일종의 window(창)) 으로 표현하여 구현을 편하게 할 수 있다는 것을 기억합니다. ( -K로 단순히 음수 표현을 하는 것을 거의 사용하지 않아서 잠시 잊고있엇는데, 해당 방안으로 할 경우 2*K + 1 대신에 더 직관적인 것 같습니다. 만약 2*K + 1을 할경우 pos의 인덱스 처리가 더 복잡해졌을 것 입니다.)

    			for(int j=-K; j<=K; j++) {
    				int pos = i + j;
    				if(pos >= 0 && pos < N && arr[pos] == 'H') {
    					answer += 1;
    					arr[i] = 'X';
    					arr[pos] = 'X';
    					break;
    				}
    			}
    		}

 

구현하며 간과할 수 있는점은, 각 Index가 0 보다 작으면 안되고, N 보다 커져서는 안됩니다.

for(int j=-K;j<=K;j++) {
    if( i+j >= N) break;
    if( i+j < 0) continue;

 

코드

정답코드1입니다.

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


public class Main {
	
	public static int N, K;
	public static char[] arr;
	public static boolean[] visited;
	public static int answer = 0;
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	N = Integer.parseInt(st.nextToken());
    	K = Integer.parseInt(st.nextToken());
    	arr = new char[N];
    	visited = new boolean[N];
    	
    	st = new StringTokenizer(br.readLine());
    	arr = st.nextToken().toCharArray();
    	
//    	System.out.println(arr);
    	for(int i=0;i<N;i++) {
    		if(arr[i] == 'P') { //사람을 만났다면, K인 것 앞에서부터
    			for(int j=-K;j<=K;j++) {
    				if( i+j >= N) break;
    				if( i+j < 0) continue;
    				
    				if(arr[i+j] == 'H' && visited[i+j] == false) {
    					visited[i+j] = true;
    					answer += 1;
    					break;
    				}
    			}
    		}
    	}
    	
    	System.out.println(answer);
    }

    
}

 

정답코드2입니다.

package Main;

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

public class Main {
	private static int N, M, Q, K;
    private static char[] arr;
    private static int[] visited;
    private static int answer = 0;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        
        arr = new char[N];
        st = new StringTokenizer(br.readLine());
        arr = st.nextToken().toCharArray();
        func();
        System.out.println(answer);
    }
    
    
    private static void func() {
    	
    	for(int i=0; i<N; i++) {
    		if(arr[i] == 'P') {
    			for(int j=-K; j<=K; j++) {
    				int pos = i + j;
    				if(pos >= 0 && pos < N && arr[pos] == 'H') {
    					answer += 1;
    					arr[i] = 'X';
    					arr[pos] = 'X';
    					break;
    				}
    			}
    		}
    	}	
    }
    
}

 

완전탐색을 할경우 시간초과가 발생합니다.

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

public class Main {
	private static int N, M, Q, K;
    private static char[] arr;
    private static int answer = Integer.MAX_VALUE;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        
        st = new StringTokenizer(br.readLine());
        arr = st.nextToken().toCharArray();
        
//        System.out.println(1 << 0);
        answer = func(0, 1);
        System.out.println(answer);
    }
    
    // func(int n) : 순서를 반드시 앞에서 뒤로 먹는 순으로 강제해야 합니다.
    private static int func(int n, int visited) {
    	if(n >= N) return 0;
    	
    	int ret = 0;
    	
    	if( (visited & (1 << n+1)) == 0) {
	    	for(int i=1; i<=K;i++) {
	    		int nextPos = n + i;
	    		if( nextPos < N && arr[n] != arr[nextPos] && (visited & (1 << (n+1))) == 0 &&  (visited & (1 << (nextPos+1))) == 0 ) {
	    			ret = Math.max(ret, func(n + 1, visited + (1 << (n+1)) + (1 << nextPos + 1) ) + 1);
	    		}
	    	}
    	}
    	ret = Math.max(ret, func(n + 1, visited));
    	
    	return ret;
    }
    
    
}

 

메모이제이션을 적용할경우 메모리 초과가 발생합니다.

이유는 visited를 활용하여 비트마스킹으로 방문처리를 하고 있는데, 이떄 int형의 최대 범위는 2^31 으로써, visited의 경우 31 자리를 이동하면 사용이 불가합니다. 

그러나, N은 2만이므로 1 << 2 * 10^5 입니다. 너무 큰 숫자로 표현이 불가합니다.

package Main;

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

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

public class Main {
	private static int N, M, Q, K;
    private static char[] arr;
    private static int answer = Integer.MAX_VALUE;
    private static int[][] cache;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        
        st = new StringTokenizer(br.readLine());
        arr = st.nextToken().toCharArray();
        
        cache = new int[N+1][1 << 20001];
        for(int i=0;i<=N;i++)
        	Arrays.fill(cache[i], -1);
//        System.out.println(1 << 0);
        answer = func(0, 1);
        System.out.println(answer);
    }
    
    // func(int n) : 순서를 반드시 앞에서 뒤로 먹는 순으로 강제해야 합니다.
    private static int func(int n, int visited) {
    	if(n >= N) return 0;
    	
    	if(cache[n][visited] != -1) return cache[n][visited];
    	int ret = 0;
    	if( (visited & (1 << n+1)) == 0) {
	    	for(int i=1; i<=K;i++) {
	    		int nextPos = n + i;
	    		if( nextPos < N && arr[n] != arr[nextPos] && (visited & (1 << (n+1))) == 0 &&  (visited & (1 << (nextPos+1))) == 0 ) {
	    			ret = Math.max(ret, func(n + 1, visited + (1 << (n+1)) + (1 << nextPos + 1) ) + 1);
	    		}
	    	}
    	}
    	ret = Math.max(ret, func(n + 1, visited));
    	
    	return cache[n][visited] = ret;
    }
    
    
}