📌문제
닭이 길을 건너간 이유는 과학적으로 깊게 연구가 되어 있지만, 의외로 소가 길을 건너간 이유는 거의 연구된 적이 없다. 이 주제에 관심을 가지고 있었던 농부 존은 한 대학으로부터 소가 길을 건너는 이유에 대한 연구 제의를 받게 되었다.
존이 할 일은 소가 길을 건너는 것을 관찰하는 것이다. 존은 소의 위치를 N번 관찰하는데, 각 관찰은 소의 번호와 소의 위치 하나씩으로 이루어져 있다. 존은 소를 10마리 가지고 있으므로 소의 번호는 1 이상 10 이하의 정수고, 소의 위치는 길의 왼쪽과 오른쪽을 의미하는 0과 1 중 하나다.
이 관찰 기록을 가지고 소가 최소 몇 번 길을 건넜는지 알아보자. 즉 같은 번호의 소가 위치를 바꾼 것이 몇 번인지 세면 된다.
입력
첫 줄에 관찰 횟수 N이 주어진다. N은 100 이하의 양의 정수이다. 다음 N줄에는 한 줄에 하나씩 관찰 결과가 주어진다. 관찰 결과는 소의 번호와 위치(0 또는 1)로 이루어져 있다.
출력
첫 줄에 소가 길을 건너간 최소 횟수를 출력한다.
예제 입력
8
3 1
3 0
6 0
2 1
4 1
3 0
4 0
3 1예제 출력
3힌트
3번 소는 위치 1, 0, 1에서 관찰되었으므로 길을 최소 두 번 건넜음을 확인할 수 있다. 4번 소도 길을 한 번 건넜으며, 나머지 소는 길을 건넌 기록이 확인되지 않는다.
💡Idea
🐮소가 관찰될 때마다 각 소가 이전 위치와 달라졌는지를 확인하여, 달라진 횟수를 체크해야 하는 문제입니다.
소가 관찰될 수 있는 위치는 0과 1, 둘 중 하나이기 때문에 저는 양수/음수로 0과 1을 구분할 수 있도록 하여 구현해보았습니다.
💻코드1
- 시간 : 76 ms / 메모리 : 30840 KB
import sys
input = sys.stdin.readline
N = int(input())
cow = [0 for _ in range(11)] # 소 10마리에 대하여 0으로 초기화, 각 소들의 이동 횟수를 나타냄
for _ in range(N):
c, r = map(int, input().split())
if cow[c] == 0: # 처음 관찰된 소인 경우 입력된 위치에 따라 1 또는 -1 저장
cow[c] = 1 if r else -1
elif r == 1 and cow[c] < 0: # 소가 이전에 0의 위치, 현재 1의 위치에 있는 경우
cow[c] = -cow[c] + 1
elif r == 0 and cow[c] > 0: # 소가 이전에 1의 위치, 현재 0의 위치에 있는 경우
cow[c] = -cow[c] - 1
print(sum([abs(c) - 1 for c in cow if c != 0])) # 각 소들의 이동 횟수를 모두 합함
📝코드 설명1
변수
N: 소의 관찰 횟수cow: 각 소의 관찰 횟수를 담은 리스트
cow 리스트의 초깃값으로는 모든 소가 0의 값을 가지고 있습니다.
그 뒤로, i번 소가 1의 위치에 있다면 cow[i]의 값은 양수, 0의 위치에 있다면 cow[i]의 값은 음수의 값을 가지게 됩니다.
그리고, i번 소가 또 다시 나오게 되었을 때, 현재의 입력된 위치와 cow[i]의 값을 비교하여 소가 이동을 했다면 절댓값 기준으로 값을 하나 증가해줍니다.
모든 입력이 끝나면, 각 소들의 이동 횟수를 모두 더하여 출력해줍니다.
💻코드2
- 시간 : 68 ms / 메모리 : 30840 KB
생각해보니, 이 문제는 각 소가 몇 번 이동했느냐를 묻는 문제가 아니라 모든 소가 이동한 총 횟수를 구하는 것입니다. (왜 처음에는 무조건 각 소의 이동 횟수를 저장해야한다고 생각했는지 모르겠네요🤣)
따라서, 굳이 각 소가 이동하는 횟수를 저장할 필요 없이, 아래와 같이 각 소의 마지막 위치만을 저장하고, 총 횟수는 변수 하나만 가지고 저장하면 조건문을 줄일 수 있습니다.
import sys
input = sys.stdin.readline
N = int(input())
cow = [-1 for _ in range(11)] # 소 10마리에 대하여 -1로 초기화
ans = 0
for _ in range(N):
c, r = map(int, input().split())
if cow[c] == -1 : # 소가 처음 관찰된 경우
cow[c] = r
elif cow[c] != r: # 소가 이전에 관찰된 위치와 다른 경우 ans 1 증가
cow[c] = r
ans += 1
print(ans)
