programmers 12949 행렬의 곱셈

개요

요즘 블로그 글을 쓰는게 엄청 뜸했는데

기록이 정말정말 중요하다는 생각에 다시 열심히 써볼려고 함!

우선은 밀린 글부터 차근차근 써나갈 예정

문제

링크 : https://programmers.co.kr/learn/courses/30/lessons/12913

땅따먹기 게임을 하려고 합니다. 땅따먹기 게임의 땅(land)은 총 N행 4열로 이루어져 있고, 모든 칸에는 점수가 쓰여 있습니다. 1행부터 땅을 밟으며 한 행씩 내려올 때, 각 행의 4칸 중 한 칸만 밟으면서 내려와야 합니다. 단, 땅따먹기 게임에는 한 행씩 내려올 때, 같은 열을 연속해서 밟을 수 없는 특수 규칙이 있습니다.

예를 들면,

| 1 | 2 | 3 | 5 |

| 5 | 6 | 7 | 8 |

| 4 | 3 | 2 | 1 |

로 땅이 주어졌다면, 1행에서 네번째 칸 (5)를 밟았으면, 2행의 네번째 칸 (8)은 밟을 수 없습니다.

마지막 행까지 모두 내려왔을 때, 얻을 수 있는 점수의 최대값을 return하는 solution 함수를 완성해 주세요. 위 예의 경우, 1행의 네번째 칸 (5), 2행의 세번째 칸 (7), 3행의 첫번째 칸 (4) 땅을 밟아 16점이 최고점이 되므로 16을 return 하면 됩니다.

풀이

이전에 밟은 땅의 점수를 의미하는 tmp 변수를 이용한다.

문제에서 이전에 밟은 땅은 연속적으로 밟을 수 없다고 하였으므로 이 부분 주의하여 이전에 밟지 않은 땅만 계산한다.

이전에 밟은 땅 점수 + 현재 밟은 땅의 점수를 계산하여 가능한 모든 경우의 수에 최대값을 계산하면 되는 문제

코드

class Solution {

    public String getNDigitNum(int n,int digit)
    {
        StringBuilder sb = new StringBuilder();
        int curNumber = n;
        if(curNumber == 0)
        {
            return "0";
        }
        while(curNumber > 0)
        {
            if(curNumber % digit < 10)
            {
                sb.append(curNumber % digit);
            }
            else
            {
                sb.append((char)(curNumber % digit - 10 + 'A'));
            }
            curNumber /= digit;
        }
        return sb.reverse().toString();
    }
    //0, 1, 1, 0, 1, 1, 1, 0, 0
    //digit,number,people,count
    public String solution(int n, int t, int m, int p) {
        String nDigitString;
        StringBuilder answerStrBuild = new StringBuilder();
        int curT = 1;
        int num=0;
        int countT = 0;
        while(true)
        {
            nDigitString = getNDigitNum(num++,n);
            for(int idx=0;idx<nDigitString.length();idx++)
            {
                if(curT == p)
                {
                    answerStrBuild.append(nDigitString.charAt(idx));
                    countT++;
                    if(countT == t)
                    {
                        return answerStrBuild.toString();
                    }
                }
                curT++;
                if(curT > m)
                {
                    curT = 1;
                }
            }
        }
    }
}

메모

문제를 잘못 이해해서 이전에 밟은 땅은 다시 안밟는다고 해석했는데 그럼 문제에 모순이 생기는데

어쨌건 해보자 해서 백트래킹으로 풀려고 했었던 기억이 남

문제에 모순이 생긴다 -> 문제를 잘못 이해한 것이므로 그냥 대충 넘어가면 안될 것 같다!