반응형
n칸의 벽 중 덧칠해야 할 칸 번호가 적힌 벡터를 참고하여, 한번에 m칸 칠할 수 있는 페인트 롤러를 이용해 최소의 페인트칠 횟수 구하는 문제.
문제의 조건을 보면 section 벡터의 크기가 무조건 1이상이므로, 최소 한번은 칠해야 한다는 점을 기억하자.
section[0]에서 시작해서 한번 칠할 때 section[0]+m-1번 칸 까지는 칠해진다.
그리고 한번 칠했으므로, 칠한 횟수(answer)를 1 증가시켜준다.
temp에 section[0]+m에 대한 값을 저장해두고, for문을 통해 section[1]부터 section의 크기만큼 순회한다.
그래서, 다음 칠해야 할 칸이, 이전에 한번 칠했던 범위에 포함이 되는지를 살펴보고, 포함이 된다면 현재 회차는 넘어가도록 한다.이는 현재 section[i]의 값이 temp보다 작은지를 보면 된다.
만약 현재 section[i]의 값이 temp와 같거나 더 크다면 이전에 칠했을 때, 같이 칠해지지 못한 것이므로, temp를 다시 section[i]+m으로 갱신해주고, 이를 기준으로 한번 더 칠하는 것이므로 answer를 1 증가 시킨다.
위 과정을 모든 section벡터 값에 대해 순회해주면 최소 페인트 칠 횟수를 반환할 수 있다!
코드는 아래와 같다.
#include <string>
#include <vector>
using namespace std;
int solution(int n, int m, vector<int> section) {
int answer = 0;
int temp = section[0] + m;
answer++;
for (int i = 1; i < section.size(); i++) {
if (section[i] < temp) {//한번 칠한것에 같이 포함이 되면
continue;//넘어간다
}
else {
temp = section[i] + m;
answer++;
}
}
return answer;
}
반응형
'CO-TE > 프로그래머스' 카테고리의 다른 글
[프로그래머스] c++ LV2 요격 시스템 풀이/접근방법 (0) | 2023.10.12 |
---|---|
[프로그래머스] c++ LV1 대충 만든 자판 (0) | 2023.09.13 |
[프로그래머스] c++ LV1 공원 산책 (0) | 2023.09.04 |
[프로그래머스] c++ LV1 추억 점수 (0) | 2023.09.01 |
[프로그래머스] c++ LV1 달리기 경주 (0) | 2023.09.01 |