백준 문제 풀이 - 소가 길을 건너간 이유 1 14467번

Joonyeol Sim👨‍🎓·2022년 4월 7일
0

백준문제풀이

목록 보기
106/128

📜 문제 이해하기

닭이 길을 건너간 이유는 과학적으로 깊게 연구가 되어 있지만, 의외로 소가 길을 건너간 이유는 거의 연구된 적이 없다. 이 주제에 관심을 가지고 있었던 농부 존은 한 대학으로부터 소가 길을 건너는 이유에 대한 연구 제의를 받게 되었다.
존이 할 일은 소가 길을 건너는 것을 관찰하는 것이다. 존은 소의 위치를 N번 관찰하는데, 각 관찰은 소의 번호와 소의 위치 하나씩으로 이루어져 있다. 존은 소를 10마리 가지고 있으므로 소의 번호는 1 이상 10 이하의 정수고, 소의 위치는 길의 왼쪽과 오른쪽을 의미하는 0과 1 중 하나다.
이 관찰 기록을 가지고 소가 최소 몇 번 길을 건넜는지 알아보자. 즉 같은 번호의 소가 위치를 바꾼 것이 몇 번인지 세면 된다.

💡 문제 재정의

소의 번호와 위치가 주어질 때 소가 길을 건너간 최소 횟소를 출력하자.

✏️ 계획 수립

파이썬의 dictionary를 이용해서 문제를 해결할 수 있다. 만약 dict에 해당 키가 없다면 초기 값을 기록한다. 만약 해당 값이 있다면 지금 들어온 위치와 원래 있던 위치를 비교한 뒤 다르다면 move count를 1올려주고 위치를 갱신한다. 위 과정을 반복하면 최소 이동 횟수를 구할 수 있다.

💻 계획 수행

import sys

if __name__ == '__main__':
    N = int(sys.stdin.readline().strip())
    cow_dict = dict()
    move = 0
    for _ in range(N):
        cow, location = map(int, sys.stdin.readline().split())
        if cow in cow_dict.keys():
            if location != cow_dict[cow]:
                move += 1
                cow_dict[cow] = location
        else:
            cow_dict[cow] = location
    print(move)

🤔 회고

문제의 내용을 그대로 구현했지만 비트 마스킹을 이용하면 더 빠른 시간에 문제를 해결할 수 있을 것 같다.

profile
https://github.com/joonyeolsim

0개의 댓글

Powered by GraphCDN, the GraphQL CDN