글 읽기 - 예외 사항이 추가적으로 있을지 궁금합니다.

sjjung1126 1년 전 0

그리디로 풀기는 했습니다.

반례 생각해보면서 출력해보았는데, 잘 떠오르지 않아, 여쭤봅니다

DP로 풀어야 될 거같다는 생각이 들기도 했는데, 그리디도 가능할거같아서 질문 남깁니다,,,

import math

input_num = int(input(''))

cnt = 0
min_cnt = 50000
num = input_num
loop_cnt = 0
first_square = 50000

while first_square > 0:
    first_square = int(math.sqrt(num))
    first_square -= loop_cnt
    while 1:
        if num == 0:
            loop_cnt += 1
            break
        if cnt == 0:
            num -= first_square*first_square
            cnt += 1
        else:
            square_num = int(math.sqrt(num))
            num -= square_num*square_num
            cnt += 1
    if min_cnt >= cnt:
        min_cnt = cnt
    num = input_num
    cnt = 0
print(min_cnt)

ai4youej 1년 전 0

반례입니다

48
Ans: 3 (16 + 16 + 16)
Out: 4

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

예외 사항이 추가적으로 있을지 궁금합니다.

sjjung1126 1년 전 0

ai4youej 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말