[코드트리 챌린지] 7주차 - Backtracking

점수 유지중...

부족한 DP를 공부하지 않아서 계속 같은 점수를 유지하고 있다.

DP에 대한 학습이 더 필요하다고 나왔다.

앞으로는 DP를 먼저 공부하고 나서 남은 Backtracking, DFS, BFS문제를 풀어야겠다.

 

2명의 도둑 

문제 링크: https://www.codetree.ai/missions/2/problems/two-thieves?&utm_source=clipboard&utm_medium=text

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

4시간 넘게 고민을 하고 토론탭에서 도움을 받아 해결했다.

31번 테스트케이스가 통과되지 않았었는데, 내 경우에는 고른 영역의 무게가 C보다 클 때 처리하는 방법이 문제였다.

나는 처음에 무게가 가장 큰 물건을 우선적으로 포함하도록 했었다.

예를 들어 [9, 8, 4, 3, 2, 1] 영역을 골랐는데 C가 23이라면 9, 8, 4, 2가 선택되도록 했었다.

하지만 이렇게 하는 것이 항상 최대의 가치를 선택하게 하는 것은 아니었다.

그래서 모든 경우의 수를 고려해 최대 가치를 찾도록 코드를 수정하였더니 테스트케이스를 통과할 수 있었다.

 

아래는 본인이 작성한 테스트케이스를 완벽히 통과한 코드이다.

N, M, C = map(int, input().split())
rooms = [
    list(map(int, input().split()))
    for _ in range(N)
]

def findMaxVal(weights, selected_w, weight, value):
    '''최대 가치를 찾는 함수'''
    global C, max_value
    if len(weights) == 1:
        if weight + weights[0] <= C and value + weights[0]**2 > max_value:
            max_value = value + weights[0]**2
        elif weight <= C and max_value < value:
            max_value = value
        return
    findMaxVal(weights[1:], selected_w + [weights[0]], weight + weights[0], value + weights[0]**2)
    findMaxVal(weights[1:], selected_w, weight, value)

def thief1(cur_i):
    global max_value, selected_i, selected_j
    if cur_i == N:
        return
    cur_j = 0
    while cur_j <= N - M:
        weight = 0
        weights = []
        for k in range(M):
            weight += rooms[cur_i][cur_j + k]
            weights.append(rooms[cur_i][cur_j + k])
        if weight <= C:
            value = 0
            for i in range(M):
                value += weights[i] ** 2
            if value > max_value:
                max_value = value
                selected_i, selected_j = cur_i, cur_j
        else: # 무게가 C보다 크면
            before_maxV = max_value
            findMaxVal(weights, [], 0, 0)
            if before_maxV < max_value:
                selected_i, selected_j = cur_i, cur_j
        cur_j += 1
    thief1(cur_i + 1)

def thief2(cur_i):
    global max_value, selected_i, selected_j
    if cur_i == N:
        return
    cur_j = 0
    if cur_i == selected_i:
        while cur_j <= selected_j - M:
            weight = 0
            weights = []
            for k in range(M):
                weight += rooms[cur_i][cur_j + k]
                weights.append(rooms[cur_i][cur_j + k])
            value = 0
            if weight <= C:
                value = 0
                for i in range(M):
                    value += weights[i] ** 2
                if value > max_value:
                    max_value = value
            else: # 무게가 C보다 크면
                before_maxV = max_value
                findMaxVal(weights, [], 0, 0)
            cur_j += 1

        cur_j = selected_j + M
        while cur_j <= N - M:
            weight = 0
            weights = []
            for k in range(M):
                weight += rooms[cur_i][cur_j + k]
                weights.append(rooms[cur_i][cur_j + k])
            value = 0
            if weight <= C:
                value = 0
                for i in range(M):
                    value += weights[i] ** 2
                if value > max_value:
                    max_value = value
            else: # 무게가 C보다 크면
                before_maxV = max_value
                findMaxVal(weights, [], 0, 0)
            cur_j += 1

    else:
        while cur_j <= N - M:
            weight = 0
            weights = []
            for k in range(M):
                weight += rooms[cur_i][cur_j + k]
                weights.append(rooms[cur_i][cur_j + k])
            value = 0
            if weight <= C:
                value = 0
                for i in range(M):
                    value += weights[i] ** 2
                if value > max_value:
                    max_value = value
            else: # 무게가 C보다 크면
                before_maxV = max_value
                findMaxVal(weights, [], 0, 0)
            cur_j += 1
    thief2(cur_i + 1)

res = 0
max_value = 0
selected_i, selected_j = 0, 0
thief1(0)
res += max_value

max_value = 0
thief2(0)
res += max_value

print(res)