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

해당 문제는 phython에서 시간 초과가 나서 pypy3으로 제출하였다.

---

문제 설명

 

cur은 현재 계란의 위치를 의미한다. 만약 현재 위치가 eggs 배열의 범위에서 벗어날 경우 깨진 계란의 수를 세어 max_count값과 비교한다.

 

 

만약 해당 위치의 계란이 깨졌을 경우 다음 계란으로 넘어가고 해당 계란이 깨지지 않았을 경우 다른 깨지지 않은 계란들을 하나씩 쳐본다. flag는 다른 계란들이 모두 깨져서 칠 계란이 없을 경우 False값을 가지고 하나라도 칠 계란이 있으면 True값을 가진다.

 

 

전체 코드

eggs = []
max_count = 0

def func(eggs,cur):
    global max_count
    if cur == len(eggs):
        count = 0
        for i in range(len(eggs)):
            if eggs[i][0] <= 0:
                count += 1
        if count > max_count:
            max_count = count
        return

    if eggs[cur][0] <= 0:
        func(eggs,cur+1)
    else:
        flag = False
        for i in range(len(eggs)):
            if i == cur or eggs[i][0] <= 0:
                continue
            eggs[cur][0] -= eggs[i][1]
            eggs[i][0] -= eggs[cur][1]
            flag = True
            func(eggs,cur+1)
            eggs[cur][0] += eggs[i][1]
            eggs[i][0] += eggs[cur][1]
        if not flag:
            func(eggs, cur+1)
    return



def main():
    global eggs
    N = int(input())
    while N:
        N -= 1
        tmp = list(map(int,input().split()))
        eggs.append(tmp)
    func(eggs,0)
    print(max_count)
    return



if __name__ == "__main__":
    main()