백준_19941 햄버거 분배(자바) / 그리디 알고리즘

시간&메모리 제한

---

문제

---

입력&출력

---

문제풀이

package com.Back;

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

public class Back_19941 {

	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 K = Integer.parseInt(st.nextToken());
		boolean[] visited = new boolean[N];
		ArrayList<Integer> ham = new ArrayList<Integer>();
		int ans=0;
		
		String temp = br.readLine();
		for (int i = 0; i < N; i++) {
			if(temp.charAt(i)=='H') {
				ham.add(i);
				visited[i]=true;
			}
		}
		
		for (int i = 0; i < ham.size(); i++) {
			for (int j = ham.get(i)-K; j <= ham.get(i)+K; j++) {
				if(j<0 || j>=N)continue;
				if(visited[j]==false) {
					visited[j]=true;
					ans++;
					break;
				}
			}
		}
		System.out.println(ans);
	}
}

 

- 사람이 먹을 수 있는 범위를 주어지고 최대로 몇개를 먹을 수 있는지 찾는 문제입니다.

 

- 저는 생각을 달리 해서 햄버거가 사람을 픽하는 형식으로 문제풀이를 진행했습니다.

 

- visited를 만들어서 햄버거 그리고 픽을 당한 사람의 경우 true 값을 줬습니다.

 

- 햄버거의 수 만큼 for문을 돌려서 가장 왼쪽부터 확인을 해줬으며, 선택되지 않은 사람의 경우에 카운트를 해줬습니다.