[프로그래머스/Lv.1] 덧칠하기

 

https://school.programmers.co.kr/learn/courses/30/lessons/161989

프로그래머스

class Solution {
    public int solution(int n, int m, int[] section) {
        int answer = 0;
        int paint = 0; // 완료된 영역 담을 수
        
        for(int i : section) {
            if(i > paint) {
                paint = i + m - 1;
                answer++;
            } else continue;
        }        
        return answer;
    }
}

 

너무 어렵게 생각하면서 긴시간 헤매고헤매다가,, 쉽게 풀 수 있는 문제임을 깨닫고 고쳐서 맞았다ㅠㅠㅠ

처음 생각했던건 전체 칸과 길이가 같은 boolean 배열에 칠해야하는 칸은 true로 바꿔놓고 시작 -> 앞에서부터 검사하다가 true 만나면 칠할 수 있는 길이만큼 false로 바꿈 -> 여전히 true인 배열이 남아있다면 뒤에서부터 검사하다가 true 만나면 칠할 수 있는 길이만큼 false로 바꿈 -> 여전히 true인 배열 남아있다면 앞에서부터 -> 다시 뒤에서 반복반복

 

지금 dfs를 공부하느라 boolean 배열에 넣어서 체크하면 좋겠단 생각이 들기도 했고 벽이 엄청엄청 길다면 양쪽에서 처리하고 중간으로 다가오며 답을 찾는게 제일 나은 답일거라고 생각하기도 했다 그리고 앞에서부터 칠해가면 벽 길이를 넘어가는 경우도 생기지않나? 생각하기도했고,,

너무 어렵게 생각하지말고 최대한 쉽게 풀 수 있는 방법을 찾는 연습도 해야될거같다 시간만 엄청 날렸다ㅠㅠ

 

아무튼 최종적으로 푼 방법은 그냥 앞에서부터 처리하면 되는거였다 처음 만난 부분부터 칠해줄 수 있는 길이만큼 칠해주고 넘어가서 아직 안칠해진 부분 칠하면 되고 그거를 반복하면된다!

예를 들어 2에서 4만큼 칠했다면 2,3,4,5 해서 5까지 칠해지는거고

칸 숫자 기준으로 "시작칸 + 칠하는 길이 - 1" 까지 완료 -> 완료된 다음(시작칸+칠하는길이)부터 다시 칠하기!