누적합 2

[백준-파이썬] 20159: 동작 그만. 밑장 빼기냐.

문제로 가기 문제 소개, 아이디어 정훈이 -> 상대방의 순서로 카드를 윗장부터 하나씩 분배하고 있다. 카드 합이 더 큰 사람이 이긴다. 밑장 빼기를 최대 1번 해서, 정훈이가 얻을 수 있는 최대 카드 합을 구하는 문제이다. 밑장 빼기 최대 1번이니까 할 수도 있고, 안 할 수도 있는 것이다. 일단 안할 때 정훈이가 얻는 카드 합을 구했다. 그걸 ans에 대입했다. 그리고 밑장을 뺄 경우를 따져보면서, 각각의 상황에서 정훈이가 얻는 카드 합을 ans과 비교해서, 클 때의 값을 ans에 넣었다. 그러면 밑장 뺄 때 정훈이가 가진 카드의 합이 어떻게 되는지는 어떻게 구했을까? 일단 그림을 그려봤다 ! 정훈이 차례에 밑장을 빼면, 그 때를 포함해서 이후의 원래 상대가 가질 예정이었던 카드의 합과 정훈이가 가질 ..

[백준-파이썬] 20440: 니가 싫어 2

문제 보러 가기! 얼마 전에 누적합을 처음 공부하고, 관련된 문제를 풀고 싶어서 스터디 문제에 추가했다.(한 사람 당 한 문제씩 추가하는 방식으로 스터디를 하는 중입니다~) 그런데 단순한 누적합..만으로는 해결할 수 없었다..ㅠㅠ 0 ≤ 모기의 입장 시각 < 모기의 퇴장 시각 ≤ 2,100,000,000... 너무 컸기 때문이다. 그래서 계속 시간 초과, 메모리 초과..와 싸우다가 스터디를 할 때까지 못 풀었다. 스터디원 분께서 설명해주셔서 값, 좌표 압축이라는 아이디어를 처음 알게 되었다! 그 아이디어를 적용하고, 다른 부분도(이것도 아래에서 설명하겠다.) 바꾸니까 문제를 풀 수 있었다 ! 전에 코드(시간 초과) 💥 import collections import sys input = sys.stdin...

728x90