C# 마법의 엘리베이터 - DFS / 프로그래머스 [Lv.2]

출처: 프로그래머스 코딩 테스트 연습
https://school.programmers.co.kr/learn/courses/30/lessons/148653

 

 

나의 풀이

public int solution(int storey) 
{
    int minValue = int.MaxValue;
    string str = storey.ToString();
    DFS(str, str.Length - 1, 0, 0, ref minValue);

    return minValue;
}

private void DFS(string str, int i, int count, int reversed, ref int minValue)
{
    if(i == -1) // 탐색 완료
    {
        count += reversed;
        minValue = count < minValue ? count : minValue;
        return;
    }

    int num = str[i] - '0' + reversed;
    DFS(str, i - 1, count + num,      0, ref minValue);
    DFS(str, i - 1, count + 10 - num, 1, ref minValue);
}

각 버튼은 자릿수 값 n 만큼 누르거나, 값을 빼는 것도 가능해서 10 - n번 눌러도 된다.

그러나 10 - n으로 빼는 방식을 선택했다면 그 다음 자릿수에서 값이 1 더 필요한게 핵심.

 

그러나 1이 더 필요하다고해서 바로 카운트에 +1 해버리면 안된다.

앞자리가 9 였을 경우에는 +1되면 0이 되기 때문. 

offset 이라는 변수로 1을 넘긴다음, 다음 자릿수에서 계산을 한다.

 

루프를 빠져나올때는 앞자리가 없으니 바로 카운트에 +1해준다.

 

나는 string으로 변환한다음에 다시 숫자로 변환하는 방식을 썼지만

극한으로 최적화 한다면 매번 10으로 나누는 방식을 사용하면 된다.