[IT/코딩테스트] 99클럽 코테 스터디7일차 TIL + BOJ1967

 

오늘의 문제

https://www.acmicpc.net/problem/1697

 

문제가 짧아서 그런지 ㅎㅎ 뭔가 쉬워보였던 첫 만남😸

그렇지만 역시나 권장 시간인 1시간 15분을 훌쩍 넘겨 거의 2시간이 다 되어서 풀었다...

정답 비율이 26.283% ... 악랄한 무언가가 문제에 숨겨져 있다^^

 

원래 코테용 연습장에 샤프로 그려가면서 풀어보는데 아놔.. 카공하러 갔다가 연습장을 두고 와서... ㅎㅎ

급하게 스터디 플래너 맨 뒤에 있는 줄연습장에 적으면서 풀었다 ㅋㅋㅋㅋ 

 

---

나의 첫 번째 ~ 두 번째 풀이 (실패)

처음에는 어제 풀었던 bfs 정의 함수를 이용해서 풀어야겠다고 생각해서 visited 와 방문한 노드에 값을 주는 부분을 True, False 로 주었다. 그런데 그렇게 적고 보니 아무리 생각해도 몇번째에 해당 숫자를 찾았는지 표현하는 방법을 생각할 수가 없었다.

import sys
from collections import deque

n, k = map(int, sys.stdin.readline().split())
visited = [False]*(k+1)

def bfs(v):
    queue = deque([v])
    visited[v] = True
    while queue:
        x = queue.popleft()
        for i in (x-1, x+1, x*2):
            ????????

print(bfs(n))

 

 

그렇게 고민을 하면서 메모장에 열심히 그림을 그렸고. 어느 순간에 어??? 싶더니 해결 방안을 찾을 수 있었다.

 

세가지 연산법을 각각 수행해서 나온 3가지 노드 한 줄을 하나의 차례라고 생각하고.

세가지 수행이 모두 끝날 때마다 1씩 증가시키면 몇 번 수행을 해서 원하는 결과가 나왔는지 계산할 수 있다.

 

아래 노드 그림 주목

 

 

그렇게 연산을 돌리다가 원하는 값이 나오면 리턴해주는 것이다...! 🤭🍀

 

이것이다!! 이것이다!!!    라면서 호기롭게 파이참에 넣었는데.

 

아래의 오류가 발생 😂

인덱스 설정을 잘못한 것이 분명했다.

 

 

 

오답 원인 파악 하기

문제에서 보면  n 과 k 모두  0 이상 100,000 이하로 정의하고 있다.

그래서 max_num 으로 100,000 라고 해두었고 visited 를 [0] * max_num 으로 해두었는데, 

visited[max_num] 인 경우엔 설정한 범위에서 1 이 더 커지기 때문에 오류가 난 것 같다. 

 

그래서 그 부분을 그냥 수정해주었다 👍

 

 

 

 

해결 방안

import sys
from collections import deque

n, k = map(int, sys.stdin.readline().split())
max_num = 100000
visited = [0] * (max_num+1)


def bfs(v):
    queue = deque([v])
    while queue:
        x = queue.popleft()
        if x == k:
            return visited[x]
        for i in (x - 1, x + 1, x * 2):
            if (0 <= i <= max_num) and (visited[i] == 0):
                visited[i] = visited[x] + 1
                queue.append(i)


print(bfs(n))

 

 

 

 

그림을 그리면서 어쩌다가 풀이를 떠올린 것이 마음에 들었다 ㅎㅎ

이해도 잘 되었고 🥹

 

내일 문제는 아마 골드...?

내일도 풀이 방법이 시원하게 떠올랐으면 좋겠다

 

하나하나 차근차근 알아가고 있는 것 같아서 뿌듯하다🍀

---

오늘 한 공부

1. 코테 1문제

2. 대규모 시스템 설계 기초 : 4장 읽기

3. 영어 보카 DAY11

+ 외부 다른 일이 하나 있어서 많이 못했다 ㅎㅎ

 

오랜만에외출