2026/07/06 TIL

오늘의 목표

코드카타

UI 아이템 슬롯 연동

 

---

 

코드카타

 

[문제] 덧칠하기

 

<내 풀이>

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>

bool Is_painting_completed(int painted[], section_len)
{
    for (int i = 0; i < section_len; ++i)
    {
        if (!painted[i])
        {
            return false;
        }
    }
    
    return true;
}

// section_len은 배열 section의 길이입니다.
int solution(int n, int m, int section[], size_t section_len) {
    int answer = 0;
    
    int painted[] = {1};
    int section_index = section[0];

    // 디버그용 출력
    for (int i = 0; i < section_len; ++i)
    {
        printf("painted[%d] : %d", i, painted[i]);
    }
    
    // 모두 칠해져있는지 확인
    while(!Is_paintin_completed)
    {
        for (int i = section_index; i < section_len + n; ++i)
        {
            painted[i] = 1;
        }
    }
    
    return answer;
    
    
}

 

[사고 과정]

int painted[] 배열에 칠해진 벽은 1, 칠해지지 않은 벽은 0으로 넣어서 아직 칠해지지 않은 벽을 차례대로 칠하려고 했다.

페인트칠이 완료되었는지 Is_painting_completed() 함수를 통해서 반복문 안에서 매번 확인하려고 했다.

 

[해답]

#include <stdio.h>

int solution(int n, int m, int section[], size_t section_len)
{
	int answer = 0;
    int current_painted_end = 0;
    
    for (int i = 0; i < section_len; ++i)
    {
    	if (section[i] > current_painted_end)
        {
        	// 새로운 롤러질 시작 (횟수 증가)
            answer++;
            // 롤러가 닿는 마지막 지점 갱신
            current_painted_end = section[i] + m - 1;
           	
        }
    }
    return answer;
}

 

그리디 알고리즘을 적용.

그리디 알고리즘을 적용할 수 있는 조건

1. 탐욕적 선택 속성 : '지금의 최선의 선택'이 전체 최선에 포함.

2. 최적 부분 구조 : 부분 문제의 최적해가 전체 최적해의 일부

 

이번 문제의 경우 칠해지지 않은 벽을 하나씩 칠하는 것이 전체 최선의 선택이자, 전체 최적해의 일부가 된다.

따라서 그리디 알고리즘 적용 가능.