[백준] 1193. 분수찾기

1193번: 분수찾기

입출력 예시를 봐야 지그재그가 어떤 방향으로 이뤄지는 지 알 수 있으니 링크를 클릭해서 전체 예시를 봐주세요!

---

이 문제는 처음에 dfs로 방향 이동하는 걸로 풀었다가 시간 초과가 나서 인터넷으로 더 간단한 풀이방법을 검색해서 다시 풀었다.

우선 아래가 내가 처음에 dfs 활용해서 푼 버전.
정답은 잘 나왔는데, 재귀를 사용하는 이상 어떻게 해도 시간 초과가 나올 수밖에 없는 구조였다.
return을 조건문과 반복문 중간중간에 넣어 빠르게 빠져나오게 해도 어쩔 수 없었다.

# 1193 분수 찾기
def find_num(y, x, cnt, str):
    dy = [1, -1]
    dx = [-1, 1]

    if cnt == N:
        print(arr[y][x], end='')
        return
        
    # case [0] 좌하향
    # case [1] 우상향

    for i in range(2):
        if (y + dy[i]) + (x + dx[i]) == y + x:
            if y + dy[i] < 0 or x + dx[i] < 0 :continue
            if y + dy[i] >= 10000 or x + dx[i] >= 10000 :continue
            if MAP[y + dy[i]][x + dx[i]] == -1: continue
            MAP[y + dy[i]][x + dx[i]] = -1
            find_num(y + dy[i], x + dx[i], cnt + 1, str + '({},{})'.format(y + dy[i], x + dx[i]))
            return

    # case [2] x + 1: 우측 이동
    if y == 0 and x + 1 < 10000:
        MAP[y][x + 1] = -1
        find_num(y, x + 1, cnt + 1, str + '({},{})'.format(y, x + 1))
        return

    # case [3] y + 1: 아래 이동
    elif x == 0 and y + 1 < 10000:
        MAP[y + 1][x] = -1
        find_num(y + 1, x, cnt + 1, str + '({},{})'.format(y + 1, x))
        return

    return



arr = [[0 for _ in range(10000)] for t in range(10000)]
MAP = [[0 for _ in range(10000)] for t in range(10000)]

for y in range(10000):
    for x in range(10000):
        arr[y][x] = '{}/{}'.format(y+1, x+1)

N = int(input())
cnt = 1
str = '(0,0)'
MAP[0][0] = -1
find_num(0, 0, cnt, str)

# DFS로 풀었더니
# 시간초과 난다.

그래서 내가 푼 방식 말고, 아예 새로운 방식으로 접근해야겠다고 생각해 검색했더니 지그재그 되는 라인이 음수인지, 짝수인지 여부를 활용해 문제를 간단히 푸신 분이 있어 그분의 풀이를 참고했다.(https://hongcoding.tistory.com/3)

[백준] 2110번 공유기 설치 (Python 파이썬)

참고해서 다시 푼 코드는 아래와 같다. 이번에는 무난히 통과했다!

# 그래서 다른 분들의 풀이를 찾아봤더니 완전 쉽게 푸는 방법이 있었다..!
# (https://hongcoding.tistory.com/33)
# 라인이 짝수인지/홀수인지로 방향을 결정해서 푸는 방식이었다.

N = int(input())
line = 0
end = 0

# line이 1일때 숫자 1개, line이 2일때 숫자 2개 이런 식으로 늘어나므로
while N > end:
    line += 1
    end += line

# N = 14일 때 end(라인의 끝값) = 15가 나온다.
# end와 N의 차이는 1이다.
# end 안의 분수는 line이 짝수일 경우 'line/1'이 나올 것이고, line이 홀수일 경우 '1/line'이 나온다.
# line이 짝수일 때 end로 갈 수록 분자는 +1, 분모는 -1 된다.
# line이 홀수일 때 end로 갈 수록 분자는 -1, 분모는 +1 된다.

diff = end - N
if line % 2 == 0:
    top = line - diff
    bottom = 1 + diff
else:
    top = 1 + diff
    bottom = line - diff

print('{}/{}'.format(top, bottom))

수학이나 알고리즘을 잘 하는 사람들은 코드를 짜기 전에 Pseudo code로 어떻게 풀지를 다 작성한 후에 코딩에 들어간다는 이야기를 들었는데, 나는 아직도 '이렇게 저렇게 풀면 되지 않을까?' 하고 생각만 하면 바로 뛰어들어버려서 쉽게 풀 수 있는 것도 시간을 너무 많이 들여버리는 것 같다. 반성중.