백준 16987 [계란으로 계란치기] 파이썬

https://www.acmicpc.net/problem/16987

 

# 백준 16987 계란으로 계란치기

N=int(input())
eggs=[]
eggs_break=[False for _ in range(N)]
ans=0

for _ in range(N): #계란 정보 저장
    dur,wei=map(int,input().split())
    eggs.append([dur,wei])


def strike_egg(curr,cnt): #현재 손에 쥐고 있는 계란 정보와 현재 깨진 계란 정보를 인자로 받음
    global ans 
    ans=max(ans,cnt) #가장 많이 깨진 경우 확인
    if curr==N: #가장 오른쪽 계란까지 확인했다면 더이상 탐색하지 않음
        return
    if not eggs_break[curr]: #만약 손에 쥐고 있는 계란이 깨지지 않았다면
        for i in range(N):
            if not eggs_break[i] and not (i==curr): #손에 쥐고 있는 계란도 안깨지고, 목표로하는 i번째 계란도 안깨졌다면
                eggs[curr][0]-=eggs[i][1]
                eggs[i][0]-=eggs[curr][1]
                curr_break=False
                i_break=False
                if eggs[curr][0]<=0: #손에 쥐고 있는 계란이 이번 치기로로 깨졌다면
                    eggs_break[curr]=True
                    cnt+=1
                    curr_break=True
                if eggs[i][0]<=0: #목표로하는 i번째 계란이 이번 치기로로 깨졌다면
                    eggs_break[i]=True
                    cnt+=1
                    i_break=True
                strike_egg(curr+1,cnt) #다음번 순서 계란으로 탐색
                eggs[curr][0]+=eggs[i][1] #원상복구
                eggs[i][0]+=eggs[curr][1] #원상복구
                if curr_break: # 계란이 깨졌었다면 다시 원상 복구
                    eggs_break[curr]=False
                    cnt-=1
                if i_break:
                    eggs_break[i]=False
                    cnt-=1
    else:
        strike_egg(curr+1,cnt) # 손에 쥐고 있는 계란이 깨졌다면 다음번 계란으로 탐색

strike_egg(0,0) #제일 왼쪽 계란부터 시작

print(ans)

 

 

GPT의 최적화 코드이다.

별반 차이 없다.

 

다음번에 유의할 점

1. 변수사용 배열 생성 꼭 필요한지

2. 재귀적으로 진행될때 함수에 +1,-1 추가하여 인자 전송

N = int(input())
eggs = [list(map(int, input().split())) for _ in range(N)]  # 내구도, 무게 저장

ans = 0  # 최댓값 저장

def strike_egg(curr, cnt):
    global ans
    if curr == N:  # 마지막 계란까지 다 확인했다면 종료
        ans = max(ans, cnt)
        return

    # 현재 계란이 이미 깨졌다면 다음 계란으로
    if eggs[curr][0] <= 0:
        strike_egg(curr + 1, cnt)
        return

    broken = False  # 현재 턴에서 계란을 깬 적 있는지 확인

    for i in range(N):
        if i != curr and eggs[i][0] > 0:  # 자신이 아닌 깨지지 않은 계란 찾기
            # 현재 계란으로 i번째 계란을 친다
            eggs[curr][0] -= eggs[i][1]
            eggs[i][0] -= eggs[curr][1]

            new_cnt = cnt + (eggs[curr][0] <= 0) + (eggs[i][0] <= 0)  # 깨진 계란 개수 갱신
            strike_egg(curr + 1, new_cnt)  # 다음 계란으로 이동

            # 원상복구 (백트래킹)
            eggs[curr][0] += eggs[i][1]
            eggs[i][0] += eggs[curr][1]
            broken = True

    # 만약 한 번도 다른 계란을 칠 수 없었다면, 그냥 다음 계란으로 이동
    if not broken:
        strike_egg(curr + 1, cnt)

strike_egg(0, 0)
print(ans)