글 읽기 - 1463 1 만들기 질문입니다

alsdn74123 2년 전 0

우선순위를 정해서 연산을 진행했습니다

1. 2의 거듭제곱이라면 2로 나누기

2. 1을 빼서 3으로 나눠진다면 1을 빼기

3. 3으로 나눠진다면 3으로 나누기

4. 1을 뺴서 2로 나눠진다면 1을 빼기

5. 2로 나눠진다면 2로 나누기

6. 1 빼기

이런 식으로 우선순위를 정해봤습니다

하지만 제출해보니 틀렸습니다가 떴습니다

테스트 케이스, 또 다른 숫자를 넣어보고 생각해 보았는데 어디서 틀린 것인지 감이 안옵니다 반례가 있을까요???

def make_1(N):
    if not (N & (N-1)):
        return N//2
    elif (N-1)%3 == 0:
        return N - 1
    elif N%3 == 0:
        return N//3
    elif (N-1)%2 == 0:
        return N - 1
    elif N%2 == 0:
        return N//2
    else:
        return N - 1

N = int(input())
c = 0
while True:
    if N == 1:
        break
    c += 1
    N = make_1(N)

print(c)

bamgoesn 2년 전 2

반례 몇 가지 드립니다.

그리디적 접근을 시도하신 건 좋지만, 그리디에는 언제나 그것이 정당하다는 것이 확실해야 합니다. (다만 가장 작은 반례가 40이어서 문제점을 찾기 어려울 만했다고 생각하긴 합니다)

1을 빼서 3으로 나눠진다고 해도 짝수라면 반으로 나누는 게 빠를 수도 있습니다. 물론 실제로 1을 빼는 게 빠를 수도 있겠죠.

40
정답: 5 (40 20 10 9 3 1)
출력: 6 (40 39 13 12 4 2 1)

41
정답: 6 (41 40 20 10 9 3 1)
출력: 7 (41 40 39 13 12 4 2 1)

52
정답: 6 (52 26 13 12 4 2 1)
출력: 52 (52 51 17 16 8 4 2 1)

76
정답: 6 (76 38 19 18 6 2 1)
출력: 7 (76 75 25 24 8 4 2 1)

80
정답: 6 (80 40 20 10 9 3 1)
출력: 7 (80 40 39 13 12 4 2 1)

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

문제

문제

출처

ICPC

1463 1 만들기 질문입니다

alsdn74123 2년 전 0

bamgoesn 2년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말