KiTFOx's Notepad 📝

1. 문제 요약

절댓값이 10c 형태인 정수들이 적힌 버튼
현재 층 수에 버튼에 적혀 있는 값을 더한 층으로 이동
엘리베이터가 위치해 있는 층과 버튼의 값을 더한 결과가 0보다 작으면 엘리베이터는 움직이지 않음
0층이 가장 아래층
버튼 한번 당 돌 한개
최소한의 돌 최대한으로 내려가기
10단위로 나머지 계산
2,5,5,4 -> 16
1,6 -> 1+(10-6) = 5
7~9 인 경우 반올림해서 빼는 경우가 더 이득
1~5 인 경우 그냥 빼는 경우가 이득
2000 + 500 + 50 + 4
작은 결과들을 모아서 큰 결과 값을 만들 수 있는지 확인해보기

2. 코드

#include <string>
#include <vector>

using namespace std;

//최적의 사용 돌 갯수 구해서 answer에 더해주는 함수
void GetOptimalStoneCount(int& storey,int& answer){
    int count = storey%10;
    
    if(count<5) answer+=count;
    else{
        if(count==5&&storey%100<50){
            answer+=count;
        }
        else{
            answer+=10-count;
            storey=storey+10-count;
        }
    }
    storey/=10;
    //printf("%d, %d\n",storey,answer);
}

int solution(int storey) {
    int answer = 0;

    while(storey>1){
        GetOptimalStoneCount(storey,answer);
    }
    
    return answer+storey;
}

3. 해설

제가 선택한 알고리즘의 방법은 10씩 나눈다음 해당 값이 반올림이 가능한지 아닌지를 판별하는 것을 채택했습니다.

예를 들어, 맨 끝의 자리 숫자가 6이상인 경우 -6을 통해 6번 돌을 사용하는 것보다 한자릿수를 늘려서 처리하는 것이 이득입니다. 56의 경우 5+6 = 11 보다 4+6 = 10 의 경우 1의 이득을 더 볼 수 있습니다.

이러한 로직을 바탕으로 코드를 짜게 되면 최적의 돌을 구할 수 있습니다.

다만 5의 경우 주의해야할 점이 555, 545 이 경우입니다.

545의 경우 5+4+5 = 14가 최적의 돌의 경우의 수입니다.

만약 반올림을 해버리는 경우 5+5+5 = 15가 되기 때문에 더 많은 돌을 사용하게 됩니다.

555의 경우가 제일 헷갈려서 시간을 오래쓰게 되었습니다.

555의 경우,

560 -> +5  : 5번(+1)
600 -> +40 : 4번(+10)
1000 -> +400 : 4번(+100)
0 -> -1000 : 1번(-1000)

if(count==5&&storey%100<50){
	answer+=count;
}

해당 if문을 통해 10의 자리 수가5보다 작은 경우에는 반올림을 해주지 않고 그대로 - 를 감행하고, 반대의 경우에는 반올림을 진행하여 이득을 보는 형태로 코드를 사용하였습니다.

4. 테스트 케이스

999 -> 1+1 = 2

55 -> 5+5 = 10

75 -> 5+2+1 = 8

155 -> 5+4+2 = 11

545 -> 5+4+5 = 14

555 -> 5+4+4+1 = 14