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

다시 최고 점수 달성!

이전에 찍었던 최고 점수와 동일한 점수가 다시 나왔다!

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

앞으로 계속해서 Backtracking, DFS 문제들을 풀어나가면서 완벽하게 만들고 dp를 공부해야겠다. 

 

2명의 도

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

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

4시간 넘게 고민을 했지만 아직도 해결하지 못했다.

아래는 본인이 작성한 테스트케이스를 80% 정도 통과한 코드이다.

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

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])
        value = 0
        if weight <= C:
            for i in range(M):
                value += weights[i] ** 2
        else: # 무게가 C보다 크면
            # 최대한 큰 무게들로 이루어진 조합을 찾는다.
            weights.sort()
            weight = 0
            for i in range(M-1, -1, -1):
                if weights[i] <= C - weight:
                    value += weights[i] ** 2
                    weight += weights[i]
                if weight == C:
                    break
        if value > max_value:
            max_value = value
            selected_i, selected_j = cur_i, cur_j
        cur_j += 1
        print("v:", value)
    thief1(cur_i + 1)

def thief2(cur_i):
    global max_value2
    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:
                for i in range(M):
                    value += weights[i] ** 2
            else: # 무게가 C보다 크면
                # 최대한 큰 무게들로 이루어진 조합을 찾는다.
                weights.sort()
                weight = 0
                for i in range(M-1, -1, -1):
                    if weights[i] <= C - weight:
                        value += weights[i] ** 2
                        weight += weights[i]
                    if weight == C:
                        break
            if value > max_value2:
                max_value2 = value
            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:
                for i in range(M):
                    value += weights[i] ** 2
            else: # 무게가 C보다 크면
                # 최대한 큰 무게들로 이루어진 조합을 찾는다.
                weights.sort()
                weight = 0
                for i in range(M-1, -1, -1):
                    if weights[i] <= C - weight:
                        value += weights[i] ** 2
                        weight += weights[i]
                    if weight == C:
                        break
            if value > max_value2:
                max_value2 = value
            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:
                for i in range(M):
                    value += weights[i] ** 2
            else: # 무게가 C보다 크면
                # 최대한 큰 무게들로 이루어진 조합을 찾는다.
                weights.sort()
                weight = 0
                for i in range(M-1, -1, -1):
                    if weights[i] <= C - weight:
                        value += weights[i] ** 2
                        weight += weights[i]
                    if weight == C:
                        break
            if value > max_value2:
                max_value2 = value
            cur_j += 1
    thief2(cur_i + 1)

max_value = 0
selected_i, selected_j = 0, 0
thief1(0)
print(max_value)

max_value2 = 0
thief2(0)
print(max_value2)

print(max_value + max_value2)