덧칠하기

 

vector 'wall' 를 만들어서 색칠해야 하는 부분은 1로, 색칠하지 않아도 되는 부분은 0으로 만든 후 2중 for문을 통해 몇 번 칠해야하는지를 구하는 방식으로 문제를 풀었다.

그런데 루프를 한 번만 사용해서 해결한 풀이를 확인했고 참고해서 다시 풀어보았고 이는 p.s 중 greedy 에 해당하는 접근 방식으로 보여진다.

예전에 C++강의를 들으면서 동전 거스름돈 문제를 예시로 greedy를 스쳐가듯 배웠었는데, 잘 기억이 나지 않아 문제 해결 방식을 설계할 때 떠오르지 않았던 것 같다.

 

greedy 알고리즘에 대한 추가적인 정리

https://dong-grae.tistory.com/103

Greedy 알고리즘

 

 

 

*초기 작성 코드

#include <string>
#include <vector>

using namespace std;

int solution(int n, int m, vector<int> section)
{
    vector<int> wall(n);
    int cnt = 0;

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

    for (int i = 0; i < wall.size(); ++i)
    {
        if (wall[i] == 1)
        {
            for (int j = 0; j < m; j++)
            {
                if (wall.size() > i + j) wall[i + j] = 0;
            }
            cnt++;
        }
        
    }

    return cnt;
}

• wall 이라는 배열을 추가적으로 만들어서 2중 루프를 통해 현재 wall이 '1'이라면 m번 반복해서 뒤에 wall까지 '0'으로 색칠하는 구조이다.
• 불필요한 반복이 많이 발생해 효율적이지 않다.

 

*greedy 알고리즘으로 문제 해결

#include <string>
#include <vector>

using namespace std;

int solution(int n, int m, vector<int> section) 
{
    int answer = 1;
    int pivot = section[0];
    
    for(const auto& i : section)
    {
        if(i < pivot + m) continue;
        
        pivot = i;
        answer++;
    }
    
    return answer;
}

• 처음 페인트칠 시작 위치 section[0]을 pivot에 저장하였고, 이미 pivot 위치에서 페인트칠을 했다고 가정했기 때문에 answer에 '1'의 값을 넣고 시작한다.
• section의 요소를 순회하면서, 현재 커버 범위(pivot + m) 내에 있는지 확인하고, 범위 내에 있다면 다음으로 넘어간다.
• 커버 범위를 벗어나는 요소가 나오면 횟수를 증가시키고, 현재 페인트칠 시작위치를 pivot으로 설정한다.
• 이 방식은 greedy 알고리즘을 활용해 구간 커버링 문제를 해결한 방식이라고 볼 수 있다.
• 현재 위치에서 가장 멀리 커버할 수 있는 구간(pivot + m)을 설정한 뒤, 새로운 구간이 필요할 때마다 커버 범위를 변경하면서 문제를 해결했다.