[boj 33892] 2025 만들기

 

문제 링크

 

주어진 N에 대해서, 1~N 까지의 정수를 가지고 2025라는 정수를 만들 수 있는지 묻는 문제입니다.

가능한 연산은 +, -, * 입니다.

 

케이스를 나눠보면,

 

1) N이 7보다 작으면 어떻게 해도 2025를 만들 수 없습니다.

 

2) N이 7보다 크거나 같으면 2025를 만들 수 있습니다.

N이 7일 때, 

1+4, 5*5, 2+7, 3+6, 9*9, 25*81 로 2025가 완성되며

N이 9일 때,

1+4, 5*5, 2+7, 3+6, 9*9, 25*81, 9-8, 2025*1

N 이 7 이상의 모든 홀수에서 위와 같은 방법으로 2025가 만들어지며,

마찬가지로 N이 8일 때 2025를 만들 수 있는 방법이 있으며, 따라서 모든 7보다 크거나 같은 N에 대해서 2025를 만드는 방법이 생깁니다.

 

코드는 아래와 같습니다.

 

import sys
input = sys.stdin.readline


def solve():
    N = int(input())
    
    if N < 7:
        print("NO")
        return
    
    print("YES")
    
    if N%2:
        ans = "1 + 4\n5 * 5\n2 + 7\n3 + 6\n9 * 9\n25 * 81"
        for i in range(8, N+1, 2): ans += f"\n{i+1} - {i}\n2025 * 1"
    else:
        ans = "1 + 8\n2 + 7\n9 * 9\n3 + 6\n9 - 4\n5 * 5\n25 * 81"
        for i in range(9, N+1, 2): ans += f"\n{i+1} - {i}\n2025 * 1"
            
    print(ans)
    
    return


def main():
    solve()
    
    return


if __name__ == "__main__":
    solve()

 

시간초과는 언제나 슬프다...