Lv2. 땅따먹기

문제 보기 :  땅따먹기

프로그래머스

 

---

문제

• 정답률 : 59%

---

작성 코드

def solution(land):
    answer = 0
    
    for now in range(4):
        an = land[0][now] #1
        for i in range(1,len(land)):
            kk = land[i]
            
            if kk.index(max(kk)) == now:
                kk.remove(max(kk))
                if kk.index(max(kk)) < now:
                    an += max(kk)
                    now = kk.index(max(kk))
                else:
                    an+=max(kk)
                    now = kk.index(max(kk))+1
            else:
                an += max(kk)
                now = kk.index(max(kk))
            
        if answer < an:
            answer = an
            
    return answer
    return max(answer)

처음에는 이런 식으로 뒤죽박죽으로 작성해서 런타임 에러가 났다.

근데 문제도 그렇고, 알고리즘도 DFS/BFS로 해결하는 문제인 듯 했고 다시 코드를 짜서 해결했다.

완성한 코드는 아래와 같다.

def solution(land):
    answer = 0
    an = {i:land[0][i] for i in range(len(land[0]))}

    for i in range(1,len(land)):
        ll = land[i]
        jj = {i:[] for i in range(len(land[0]))}
        new_an = {i:0 for i in range(len(land[0]))}
        for k in an:
            a = ll[k]
            if k == 0:
                jj[k].append(a+an[1])
                jj[k].append(a+an[2])
                jj[k].append(a+an[3])
            elif k == 1:
                jj[k].append(a+an[0])
                jj[k].append(a+an[2])
                jj[k].append(a+an[3])
            elif k == 2:
                jj[k].append(a+an[0])
                jj[k].append(a+an[1])
                jj[k].append(a+an[3])
            elif k == 3:
                jj[k].append(a+an[0])
                jj[k].append(a+an[1])
                jj[k].append(a+an[2])
                
        for k in jj:
            new_an[k] = max(jj[k])
        
        an = new_an
    
    answer = max(new_an.values())
    return answer

---

풀이

이중 for문에 if문을 여러개 써도 (사실 if문은 시간복잡도에 큰 영향은 없다만) 정확도만 해결하면 효율성은 알아서 해결되는 문제인 것 같았다. 아니면 내가 코드를 잘 짰을수도..?!

과정은 DFS/BFS 문제에서 항상 사용되는 "뒷 케이스 기준으로 생각하기"로 해결했다.

예시가 [[1,2,3,5],[5,6,7,8],[4,3,2,1]]일 때 이해하기 좋게 아래와 같이 두겠다. 답은 16이 나와야한다.

[[1,2,3,5]
[5,6,7,8]
[4,3,2,1]]

먼저, an이라는 딕셔너리로 1번째 리스트의 index와 값을 배분한다. {0:1, 1:2, 2:3, 3:5}
2번째 리스트부터 for문이 돌아가도록 알고리즘을 구성하는데,
1) i == 0 일 때는 an의 1,2,3을 2번째 리스트(a)의 i번째 원소와 더해서 jj[i] (즉, jj[0])에 모두 입력한다.
2) i == 1일 때는 an의 0,2,3을 선택하여 작업한다.
3) i == 2일 때는 an의 0,1,3을 선택하여 작업한다.
4) i == 3일 때는 an의 0,1,2을 선택하여 작업한다.

그리고 jj[i]마다 max값을 가지는 new_an을 만들어, 이를 an으로 재설정한다.

이렇게 알고리즘을 짜니 바로 해결되었다!