문제
마법의 세계에 사는 민수는 아주 높은 탑에 살고 있습니다. 탑이 너무 높아서 걸어 다니기 힘든 민수는 마법의 엘리베이터를 만들었습니다. 마법의 엘리베이터의 버튼은 특별합니다. 마법의 엘리베이터에는 -1, +1, -10, +10, -100, +100 등과 같이 절댓값이 10c (c ≥ 0 인 정수) 형태인 정수들이 적힌 버튼이 있습니다. 마법의 엘리베이터의 버튼을 누르면 현재 층 수에 버튼에 적혀 있는 값을 더한 층으로 이동하게 됩니다. 단, 엘리베이터가 위치해 있는 층과 버튼의 값을 더한 결과가 0보다 작으면 엘리베이터는 움직이지 않습니다. 민수의 세계에서는 0층이 가장 아래층이며 엘리베이터는 현재 민수가 있는 층에 있습니다.마법의 엘리베이터를 움직이기 위해서 버튼 한 번당 마법의 돌 한 개를 사용하게 됩니다.예를 들어, 16층에 있는 민수가 0층으로 가려면 -1이 적힌 버튼을 6번, -10이 적힌 버튼을 1번 눌러 마법의 돌 7개를 소모하여 0층으로 갈 수 있습니다. 하지만, +1이 적힌 버튼을 4번, -10이 적힌 버튼 2번을 누르면 마법의 돌 6개를 소모하여 0층으로 갈 수 있습니다.
마법의 돌을 아끼기 위해 민수는 항상 최소한의 버튼을 눌러서 이동하려고 합니다. 민수가 어떤 층에서 엘리베이터를 타고 0층으로 내려가는데 필요한 마법의 돌의 최소 개수를 알고 싶습니다. 민수와 마법의 엘리베이터가 있는 층을 나타내는 정수 storey 가 주어졌을 때, 0층으로 가기 위해 필요한 마법의 돌의 최소값을 return 하도록 solution 함수를 완성하세요.
제한조건
- 1 ≤ storey ≤ 100,000,000
입출력 예시
| storey | result |
| 16 | 6 |
| 2554 | 16 |
C#
storey를 1의 자리부터 0이 될 수 있는 가장 작은 수를 구하여 더하는 과정을 반복하면서 결과를 도출해야함.
- 0이 될 수 있는 가장 작은 수 = 5를 초과하면 10에서 뺀 값으로 계산, 5이하는 그냥 사용.
- 단, 5를 초과하면 자리올림이 발생하니까 1을 더해줘야 함 → 11에서 빼면 무조건 1을 더한 효과를 볼 수 있음
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
using System;
public class Solution
{
public int solution(int storey)
{
int answer = 0;
int len = (int)Math.Log10(storey);
for (int i = 0; i <= len; i++)
{
int digit = (int)Math.Pow(10, i);
var value = (storey % (digit * 10)) / digit;
answer += value > 5 ? 11 - value : value;
storey -= value;
}
return answer;
}
}
[실패]
5를 고려하지 않음.
- 1234는 무조건 버리는 게 이득임.
- 6789는 무조건 올리는 게 이득임. 하지만 5는 다음에 올 숫자에 따라 상황이 달라짐.
자리 올림으로 계산해주지 않고, 변동되는 수를 storey에 바로 적용해줘야 정확한 값을 찾을 수 있음
변동 되는 수를 쉽게 넣어주기 위해 storey 값을 배열에 저장하도록 함. storey 자리수보다 1자리 큰 배열을 만들어 일단 storey를 1자리씩 쪼개서 배열에 넣어줌. 1자리 큰 배열을 만드는 이유는 가장 큰 자리수의 자리 올림을 고려해서 넉넉하게 만듦.
자리 올림 시 10이 되는 경우 다시 다음 자리수로 올려주는 작업이 필요함.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
using System;
public class Solution
{
public int solution(int storey)
{
int answer = 0;
int digit = 1;
int len = (int)Math.Log10(storey);
int[] values = new int[len+2];
for (int i = 0; i <= len; i++)
{
values[i] = storey % (digit * 10) / digit;
digit *= 10;
}
for (int i = 0; i <= len; i++)
{
if (values[i] == 10)
{
values[i + 1]++;
values[i] = 0;
}
if (values[i] == 5)
{
if(values[i + 1] > 5)
{
answer += 10 - values[i];
values[i + 1] += 1; //올림처리
}
else
{
answer += values[i];
}
}
else
{
if (values[i] > 5)
{
answer += 10 - values[i];
values[i + 1] += 1; //올림처리
}
else
{
answer += values[i];
}
}
}
return answer + values[len + 1];
}
}
[실패]
1, 3번만 테스트에서 실패가 뜸. 반례를 찾아봄. 555일 때는 14가 나와야 하는데 15가 나옴.
현재 값이 5일 때 5를 초과하는 수에 대해서 자리 올림을 해주고 있었으나 5이상인 경우 자리 올림 하도록 수정함.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
using System;
public class Solution
{
public int solution(int storey)
{
int answer = 0;
int digit = 1;
int len = (int)Math.Log10(storey);
int[] values = new int[len + 2];
for (int i = 0; i <= len; i++)
{
values[i] = storey % (digit * 10) / digit;
digit *= 10;
}
for (int i = 0; i <= len; i++)
{
if (values[i] == 10)
{
values[i + 1]++;
values[i] = 0;
}
if (values[i] == 5)
{
answer += GetSumValue(values[i + 1] >= 5, values, i);
}
else
{
answer += GetSumValue(values[i] > 5, values, i);
}
}
return answer + values[len + 1];
}
private int GetSumValue(bool isCarry, int[] values, int index)
{
if (isCarry)
{
values[index + 1] += 1; //올림처리
return 10 - values[index];
}
else
{
return values[index];
}
}
}
[성공]
프로그래머스에서 문제 확인