나의 풀이.
한 번에 칠할 수 있는 길이는 m이고 다시 칠하기로 한 구역은 적어도 한 번은 페인트칠을 해야하니까
section 배열 안의 요소들이 한번씩만 칠해지는 최소 횟수를 구하면 된다. 어렵다..
section 배열은 오름차순으로 되어 있어 0번째 인덱스의 값이 첫 시작 위치가 되면 된다.
예제 1번을 예로 들면 2부터 한번에 칠할 수 있는 끝인 5가 되어야 하기때문에
end 인덱스를 section[0] + m(칠할 수 있는 길이) 하면 6에서 -1 해야 원하는 길이가 된다.
그럼 다음 section배열 요소에서 5를 넘지 않으면 다시 칠할 필요가 없기 때문에 다음 요소로 넘어간다.
section[1]의 값은 3으로 이미 칠해진 범위기 때문에 넘어간다.
다음 section[2]의 경우 6으로 칠해진적이 없기 때문에 칠하는 횟수를 +1 해주고 end를 다시 잡아준다.
answer가 1인 이유는 처음에 한 번 칠하고 뒤에 조건을 돌기 때문임
만약에 1번 예제에서 6 뒤에 9가 있어 2, 3, 6, 9 라고 가정해도 정답은 2가 된다.
6에서 + 4 - 1 한게 끝점이 되서 9도 이미 칠해졌기 때문에 2가 되는것
처음에는 그림때문에 헷갈려서 중복칠하면 안되나 했는데 그런건 아녔다.
무튼 어려운 문제다..
class Solution {
public int solution(int n, int m, int[] section) {
int answer = 1;
int end = section[0] + m - 1;
for (int i = 0; i < section.length; i++) {
if (end < section[i]) {
answer++;
end = section[i] + m - 1;
}
}
return answer;
}
}
'CODING TEST' 카테고리의 다른 글
백준 2167번 - 2차원 배열의 합 (0) | 2023.05.29 |
---|---|
백준 1254번 - 팰린드롬 만들기 (0) | 2023.05.29 |
프로그래머스 - 전국 대회 선발 고사 (0) | 2023.05.26 |
프로그래머스 - 문자열 안에 문자열 (0) | 2023.05.22 |
백준 5613번 - 계산기 프로그램 (0) | 2023.05.22 |