글 읽기 - 메모리 초과 or 시간초과 문제..

effort98 2년 전 0

여기서 계속 수정을 해도

메모리 초과나 시간초과가 계속 뜨네요..

어케 해결하는거죠..

N, K = map(int, input().split())
visit = [0 for i in range(100001)]
visit[5] = 1
a = [[5]] # 왜냐면 최대 경우의 수가 100000
b = 0
c = [5]
j = 0
while True:
    a.append([])
    for i in a[j]:
        if visit[i-1] == 0 and i-1 >=0:
            a[j + 1].append(i - 1)
            c.append(i - 1)
            visit[i - 1] = 0
        if visit[i+1] == 0 and i+1 <= 100000:
            a[j + 1].append(i + 1)
            c.append(i + 1)
            visit[i + 1] = 0
        if visit[i*2] == 0 and i+2 <= 100000:
            a[j + 1].append(i * 2)
            c.append(i * 2)
            visit[i * 1] = 0
    j += 1
    if K in a[j]:
        b = j
        break
print(b)

jih7368 2년 전 0

22행 visit[i*1] = 0에서 visit[i*2] = 1로 고치고, 14행과 18행도 visit [i - 1] = 1, visit[i + 1] = 1로 수정하셔야합니다.

지금 상황에선 visit을 체크하지 않아서 계속 같은 곳을 중복으로 탐색하게 됩니다.

그리고 임의의 값 5를 시작할 때 추가하셨는데, 5가 아니라 N을 추가해야 시작점에서부터 탐색할 수 있습니다.

visit[N] = 1

a = [[N]]

c = [N] 으로 수정하셔야겠네요. 현재 풀이에서 c는 필요없는 것 같습니다.

그리고 visit은 100000이 최대가 아닙니다. 99에서 197을 간다면 *2해서 198로 이동한 다음 -1을 하는 것이 최소시간인데, 이처럼 생각하면 visit의 최대 크기가 몇이 될지 생각해보시기 바랍니다.

N, K = map(int, input().split())
visit = [0 for i in range("""What value?""")]
visit[N] = 1
a = [[N]]
b = 0
c = [N]
j = 0
while True:
    a.append([])
    for i in a[j]:
        if visit[i-1] == 0 and i-1 >=0:
            a[j + 1].append(i - 1)
            c.append(i - 1)
            visit[i - 1] = 1
        if visit[i+1] == 0 and i+1 <= 100000:
            a[j + 1].append(i + 1)
            c.append(i + 1)
            visit[i + 1] = 1
        if visit[i*2] == 0 and i+2 <= """What value?""":
            a[j + 1].append(i * 2)
            c.append(i * 2)
            visit[i * 2] = 1
    j += 1
    if K in a[j]:
        b = j
        break
print(b)

djm03178 2년 전 0

10만을 최대로 해도 됩니다. 말씀하신 케이스는 목표가 홀수이기 때문에 발생하는 것이고 짝수가 목표이면 그보다 높이 갈 필요는 없습니다.

jih7368 2년 전 0

본 문제에는 K의 홀짝에 대한 제약조건이 없어서 10만보다 크게 잡아야하는 경우를 고려해야할 것 같습니다.

djm03178 2년 전 1

제 말씀은, 목적지가 홀수인 경우의 최댓값은 99999이며 이때에도 10만을 넘게 갈 일이 없기 때문에 10만을 죄대로 해도 된다는 의미입니다.

jih7368 2년 전 0

아 그렇군요..! 거기까진 생각을 못 했습니다. 보충해주셔서 감사합니다.

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

문제

문제

출처

ICPC

메모리 초과 or 시간초과 문제..

effort98 2년 전 0

jih7368 2년 전 0

djm03178 2년 전 0

jih7368 2년 전 0

djm03178 2년 전 1

jih7368 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말