1일 1커밋 !

1일 1PS 72일차!

📚 문제

[골드 1] - 플래그 대사 그만 좀 말해요

💡 풀이 과정

  • 간단하지만 헷갈리는 문제다.
  • 딱히 알고리즘은 필요없지만 수상하게 난이도가 높은 피지컬 문제..?


  • 우선 문제는 간단하다.

  • 매번 목표 수치가 되도록 외침해주고 동시에 뒤에 부하까지 max(0, K-i) 만큼 더해주면 풀리지만 당연히 시간초과이다.

  • 강화에 대해 로직을 살펴보면
    • 1번에서 K= 3 으로 외친다면
    • +3, +2, +1 로 강화된다.
    • 3번을 외친다면
    • +9, +6, +3 으로 강화된다.
  • 위를 살펴보면 다음 부하로 이동하면서 외침의 횟수만큼 줄어들게 된다.
    • 이는 거리가 멀어질수록 1칸당 1의 강함이 고정적으로 감소하기 때문이다!!
  • 그렇다면 우리는 현재 위치에서 추가되는 강함의 수치에서 영향을 받은 총 외침의 수를 빼주기만하면 다음 위치에서 적용받는 강함의 수치를 바로 알 수 있다!
    • i=2, k=3 에서 강함수치가 10 증가했고 이는 (0, 1, 2) 번째에서 총 4번의 외침으로 증가했다면
    • i=3 에 도착하자마자 강화되는 수치는 10-4 라는 뜻이다.
    • 여기서 다시 2번의 외침을 시전해서 총 12의 강화수치를 얻었다면 (0, 1, 2, 3) 에서 총 6번의 외침으로 12의 강함 수치를 얻었다는 것이다.
    • 하지만 K=3 이기에 0번째 외침은 i=4 에 아무런 영향을 미치지 못하기에 총 외침 횟수에서 0번째 외침 횟수를 제해야한다.

📌포인트

  • while 문을 사용해서 cnt 를 구했지만 시간초과의 요소이다.
    • if else 문을 사용하고 // 연산자를 활용하도록 하자.
  • 요소들을 연산하는 순서가 매우 중요하다.
    • 특정 i, k 값에 대해서 원하는 동작을 주석으로 작성하면서 코딩하자.

💻 코드


N, K = map(int, input().split())
P = list(map(int, input().split()))
T = list(map(int, input().split()))

flags = [0] * N

# 총 외침 횟수
cnt_shout = 0
# 외침으로 추가 강함 수치
total_shout = 0

# 앞에서부터..
for i in range(N):
    # 이전에 total_shout 를 추가해준다.
    P[i] += total_shout

    # 현재 단계에서 몇 번을 외쳐야 강해지는 가?
    # cnt = 0
    # while P[i] < T[i]:
    #     cnt += 1
    #     P[i] += K
    cnt = 0 if P[i] >= T[i] else ((T[i] - P[i] - 1) // K) + 1

    # 현재 위치에서 cnt 번 외쳐야한다.
    flags[i] = cnt

    # 외침 횟수
    cnt_shout += cnt

    # K 거리까지만 영향이 있으므로 멀리 떨어진 외침은 삭제
    # K=3, i=3 일때 (1, 2, 3) 횟수를 가지고 있다.
    if i > K - 1:
        cnt_shout -= flags[i - K]

    # 총 강함 수치 더해준다.
    total_shout += cnt * K

    # K=3, i=3 일때 다음 부하를 위해 cnt_shout 만큼 줄어들어야한다.
    total_shout -= cnt_shout


print(sum(flags))

업데이트:

댓글남기기

참고