[백준] 2223 금화 - python

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

2223번: 금화

---

코드

맞았습니다가 뜬 코드입니다.

메모리 30616KB 시간 36ms 코드길이 311B

import sys
t, x, m = map(int, sys.stdin.readline().rstrip().split())
min_n = 1e9
for i in range(m):
    d, s = map(int, sys.stdin.readline().rstrip().split())
    min_n = min(min_n, (d - 1) // s)
if min_n == 0:
    print(min_n * x)
elif t > min_n:
    print((min_n + (t - min_n)//2) * x)
else:
    print(t * x)

가장 먼저 지민이한테 도달하는 몬스터로 인해 모든 행위가 결정됩니다.

여기서 기억해야 할 포인트는 "도달" 에 있습니다.

지민이에게 도착하면 지민이가 몬스터에 공격을 당하니 도달이라는 것은 6이라면 3까지만 도달이라고 하겠습니다.

(도착은 아니라는 뜻)

 

d에 s를 나눈 몫은 도달하는 데까지 걸리는 시간을 나타냅니다.

가장 먼저 도달하는 몬스터가 모든 행위가 결정되므로 여러 몬스터가 입력된 경우 도달시간이 가장 작은 수를 구하면 됩니다.

 

하지만 도달하지 못하는 경우는 어떡할까요? 혹은 도달하고도 남는 경우는요? 그 경우의 수를 나눠보겠습니다.

가장 적은 도달시간을 min_n이라고 합시다.

 

경우 1. 도달하지 못하는 경우 

 

- d=100000 s = 1 과 같은 경우로 도달도 못하는 경우 ( t < min_n )

 -> (100000-1)//1 = 99999 이므로 t * x 이어야 합니다.

 

- d=3 , s=3 과 같은 경우로 움직이지도 못하는 경우 ( min_n == 0 )

 -> min_n = 0 이므로 0을 출력해야 합니다.

 

 경우 2. 도달하고 남는 경우

 

- d=10, s=3 , t=5 과 같이 평상적인 경우 ( t > min_n )

 -> 움직, 움직, 움직, 안움직, 움직 의 경우로 4번 주울 수 있습니다.

     min_n + (t - min_n) // 2 로 구할 수 있습니다.

     t - min_n에 2를 나눈 것은 한 사이클을 다 돈 뒤에 남은 안움직, 움직 ... 패턴을 나눠서 움직이는 횟수만 구한 것입니다.

 

 

이 밑에 부터는 눈물의 똥꼬쇼입니다...

---

모든 코드의 기본 논리입니다. 였습니다. (틀린 내용입니다. 밑에 맞는 설명이 있긴한데.. 모든 경우의 수를 고려하진 않았습니다.)

 

Try 1.

메모리초과가 뜨는 코드입니다. - 코드길이 : 521B

import sys
t, x, m = map(int, sys.stdin.readline().rstrip().split())
mon_li = [[] for i in range(m)]
for i in range(m):
    d, s = map(int, sys.stdin.readline().rstrip().split())
    for j in range(t):
        if d > s:
            mon_li[i].append(1) # 앞으로 감
            d -= s
        else:
            mon_li[i].append(0) # 뒤로 감
            d += s
gold = 0
for i in range(t):
    for j in range(m):
        if not mon_li[j][i]:
            break
        if j == m-1:
            gold += 1
print(gold * x)

---

Try 2.

위 코드에서 이중리스트를 쓴 것이 메모리를 초과시키는 것 같아 리스트 하나로 바꾸는 방법을 생각했습니다.

 

틀렸습니다가 뜨는 코드입니다. - 코드길이 : 352B

import sys
t, x, m = map(int, sys.stdin.readline().rstrip().split())
mon_li = [1 for i in range(t)]
for i in range(m):
    d, s = map(int, sys.stdin.readline().rstrip().split())
    for j in range(t):
        if d > s: # 앞으로 감
            d -= s
        else: # 뒤로 감
            d += s
            mon_li[j] = 0
print(mon_li.count(1) * x)

 

수학문제인데 너무 구현문제처럼 접근하고 있는 것 같아서 알고리즘을 다시 생각해봐야하나..? 라는 생각이 듭니다.

테스트케이스도 별로 없어서 어디서 잘못되었는지 모르겠네요.. 다음문제 먼저 풀고 마저 풀어보겠습니다.

---

- 아 멈춰있는 동안 다른 몬스터들도 뒤로 갈 것을 생각 안 했네요;;

다시 고친 그림판 알고리즘입니다.

Try 3.

틀렸습니다가 뜨는 코드입니다. - 코드 길이 : 273B

멈춰있는 동안 다른 몬스터들이 뒤로 간다고 해도 가장 가까이서 왔다갔다하는 몬스터로 인해 줍 안줍의 상태가 반복될 수 밖에 없다고 봤습니다.

그래서 가장 가까이서 왔다갔다 하는 몬스터를 구해서 min_n이라고 합니다.

남은 시간은 2로 나눠서 몇번 더 줍는지 몫으로 구합니다. min_n이 끝나면 줍지 못하는 것 부터 시작하니까 몫으로 구합니다. 그런데도 안 됩니다.

27퍼센트까지 간 것도 약간 화나기 시작합니다.

import sys
t, x, m = map(int, sys.stdin.readline().rstrip().split())
mon_li = []
mon = 0
for i in range(m):
    d, s = map(int, sys.stdin.readline().rstrip().split())
    d -= 1
    mon = d // s
    mon_li.append(mon)
min_n = min(mon_li)
print((min_n + (t - min_n)//2) * x)

 

- 다같이 멈추고 움직인다는 중요한 개념을 헷갈렸던 것 같습니다.

하지만 다같이 멈추고 움직이기 때문에 3번째 시도가 제일 말이 된다는 생각이 듭니다. 

이런식으로 모두 이동이 가장 짧은 몬스터를 위주로 모든 멈춤과 행동이 결정되기 때문입니다.

->  t < min_n 와 min_n = 0  인 경우를 고려하지 않았습니다.

---

Search 🔍

• min_n = 1e9
  가능한 최댓값이 10억 미만이라면 무한의 값으로 1e9를 이용할 수 있다고 합니다.
  1e9 = 1e9 = 1*109 = 1000000000 라고 합니다.
  2e9도 있는데, 2e9 = 2*109 = 2000000000 라고 합니다.
  특히, 2e9는 int 범위내에서 무한대 값을 나타내기 위해 사용하는 경우가 많다고 합니다.
  
  이 문제에서는 최솟값을 주기 위해 넣었습니다.
• 놓친 경우는 백준에서 도움을 받았습니다. (감사합니다...)

후기

일부러 정답률이 낮은 문제를 찾은 거긴 한데 이게 맞나 싶었습니다 ㅋㅋ 그냥 제출한 사람이 없어서 정답률이 낮은 걸 모르고.. 진짜...ㅋㅋㅋ 킹받는 문제입니다. 끝까지 밸류에러나서 깃허브에서 겨우 정답코드 찾아서 고쳤는데 왜 밸류에러가 떴는지는 아직도 의문입니다. 최솟값 구하는 방법만 리스트에서 min()함수로 구하는 것에서 min_n변수와 min() 함수로 바꾼건데.. 리스트에 안 들어가는 경우가 있나..? d가 0인 경우에 -1이 돼서 그런가..? 모르겠네요~

그런데 깃허브에서 정답코드 찾았을 때, 제가 이미 생각한 알고리즘과 너무 똑같아서 소름이 돋았습니다. 이게 맞는지 아닌지도 모르겠지만 일단 매일 한 발자국씩 가면서 어느순간 발전한 게 느껴질 때가 제일 기쁜 순간입니다. 코딩 꿀잼!