https://www.acmicpc.net/problem/1484 1484번: 다이어트 성원이는 다이어트를 시도중이다. 성원이는 정말 정말 무겁기 때문에, 저울이 부셔졌다. 성원이의 힘겨운 다이어트 시도를 보고만 있던 엔토피아는 성원이에게 새로운 저울을 선물해 주었다. www.acmicpc.net (현재 몸무게 : A)^2 - (기존 몸무게 : B)^2 = G인 'A'의 경우의 수를 찾는 것이다. G는 100,000 이하의 자연수다. 잘 생각해보면 G는 값이 정해져있는데, A / B의 값은 범위가 정해져 있지 않은 것을 알 수 있다. 2에 의거해서 어디까지 살펴봐야할지 경계조건도 설정해야하는 것을 알 수 있다. 경계조건 설정을 위해 A^2 - B^2 = (A-B)(A+B)로 인수분해를 한다. 이 때, 알..
https://www.acmicpc.net/problem/12892 12892번: 생일 선물 첫 줄에 친구의 수 N(1 ≤ N ≤ 100,000)과 미안함을 느끼게 되는 최소가격차 D(1 ≤ D ≤ 1,000,000,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 선물의 가격 P와 만족도 V(0 ≤ P ≤ 1,000,000,000, 0 www.acmicpc.net N = 100,000이고 완전탐색을 할 경우 10억의 시간이 필요하다. 따라서 TLE 발생한다. N^2에서 시간을 줄여야 할 필요가 있다. 가능한 경우의 수는 그리디, DP, 이분탐색, 두 포인터다. 정렬하게 되면, 가장 큰 값을 가지는 영역을 구하면 되는 문제로 치환이 가능하다. 항상 모든 값은 양수이기 때문에 영역의 길이가 가장 ..
import sys n,k = map(int,sys.stdin.readline().split()) my_list = list(map(int,sys.stdin.readline().split())) pre_fix = [0 for _ in range(n+1)] for i in range(0,n) : pre_fix[i+1] = pre_fix[i] + my_list[i] answer = -9876543210 for i in range(n+1) : if i+k < n+1 : answer = max(answer, pre_fix[i+k] - pre_fix[i]) print(answer) 부족했던 부분 누적합을 구할 때, 앞에 여유 칸 없이 Prefix 배열을 만들었다. 이런 이유로 Prefix의 첫번째를 빼게 되면 항..
import sys n = int(sys.stdin.readline().rstrip()) my_list = list(map(int, sys.stdin.readline().split())) s = [0 for _ in range(n + 1)] for i in range(1, n + 1): s[i] = s[i - 1] + my_list[i - 1] answer = 0 for k in range(2, n): temp = (s[k] - s[1]) + (s[-2] - s[k - 1]) answer = max(answer, temp) for k in range(2, n): temp = (s[-2] - s[k]) + 2 * (s[k - 1] - s[0]) answer = max(answer, temp) for k i..
문제 상덕이는 언덕 위에 있는 마을의 우체국에 직업을 얻었다. 마을은 N×N 행렬로 나타낼 수 있다. 행렬로 나뉘어진 각 지역은 우체국은 'P', 집은 'K', 목초지는 '.' 중 하나로 나타낼 수 있다. 또, 각 지역의 고도도 알고 있다. 매일 아침 상덕이는 마을의 모든 집에 우편을 배달해야 한다. 배달은 마을에 하나밖에 없는 우체국 'P'가 있는 곳에서 시작한다. 상덕이는 현재 있는 칸과 수평, 수직, 대각선으로 인접한 칸으로 이동할 수 있다. 마지막 편지를 배달하고 난 이후에는 다시 우체국으로 돌아와야 한다. 상덕이는 이렇게 매일 아침 배달을 하는 것이 얼마나 힘든지 궁금해졌다. 상덕이가 배달하면서 방문한 칸 중 가장 높은 곳과 낮은 곳의 고도 차이를 피로도라고 하자. 이때, 가장 작은 피로도로 모..