[프로그래머스] 덧칠하기 - c++

덧칠하기

이 문제는 n미터의 벽을 m미터의 롤러로 페인트가 벗겨진 위치에 색칠하는 최소 횟수를 구하는 문제이다.

n의 크기를 갖는 배열을 1로 초기화하여 선언한다.

vector<int> v(n, 1);

페인트가 벗겨진 부분은 0으로 바꾼다.

for(int i=0; i<section.size(); i++) {
    int now = section[i]-1;
    v[now] = 0;
}

이미 페인트가 칠해져있다면 건너뛰고
페인트가 칠해져 있지 않은 위치부터 m미터의 롤러질 하여 페인트를 칠한다.

이때 now+m의 크기가 n미터를 초과하면 오류가 발생하므로 now+m의 크기가 벽을 초과하지 않는 한에서 롤러질을 한다.

for(int i=0; i<section.size(); i++) {
    int now = section[i]-1;
    if (v[now] == 1) continue;
    else {
        if (now+m < n) {
            for(int i=now; i<now+m; i++) {
                v[i] = 1;
            }
            answer++;
        }
    }
}

하지만 이렇게 할 경우 페인트가 벗겨졌으나 범위초과(n미터)로 인해 페인트칠을 하지 않은 벽의 부분이 생기게 된다.

그러한 부분을 처리하기 위해 색칠되지 않은 부분의 개수를 합하고,
색칠해야될 부분의 개수가 롤러크기(m미터)보다 작거나 같은 경우 페인트칠을 한번 더 해준다.

int tmp = 0;
for(int i: v) {
    if (i==0) tmp++;
}
if (tmp>0 && tmp<=m) answer++;

[전체코드]

#include <string>
#include <vector>
#include <iostream>

using namespace std;

int solution(int n, int m, vector<int> section) {
    int answer = 0;
    vector<int> v(n, 1);
    
    for(int i=0; i<section.size(); i++) {
        int now = section[i]-1;
        v[now] = 0;
    }
    
    for(int i=0; i<section.size(); i++) {
        int now = section[i]-1;
        if (v[now] == 1) continue;
        else {
            if (now+m < n) {
                for(int i=now; i<now+m; i++) {
                    v[i] = 1;
                }
                answer++;
            }
        }
    }
    int tmp = 0;
    for(int i: v) {
        if (i==0) tmp++;
    }
    if (tmp>0 && tmp<=m) answer++;
    
    return answer;
}