15487번: A[j]-A[i]+A[l]-A[k] (acmicpc.net) 크기 N인 주어진 배열 A에서 i N은 최대 1000000이라 4중 for문으로 찾는건 당연히 불가능하다 A[j] - A[i]의 최댓값과 A[l] - A[k]의 최댓값을 나눠서 구하면 좋을 것 같다 근데 i 어떻게 구할 수 있을까? 현재 0 ~ j 구간을 보고 있을때 A[j] - A[i]의 최댓값은, A[j] - (A[0] ~ A[j-1]중 최솟값) dp[j] = i j = 0, 1, 2, 3, ... 가면서 A[j]의 최솟값을 min_value로 항상 갱신해놓는다면, 현재 j에 대해 0~j-1까지 최솟값은 min_value이고 그러므로 A[j] - min_value로 최댓값을 구할 수 있다. 이를 dp[j]에 저장해놓고 ..
1. 문제 n명의 아이는 연속 A[i]일 이내 칭찬을 듣지 못하면 기분이 안좋아진다. (i = 1,2,3,...,n) 선생님이 1일부터 m일까지 매일 1명의 아이 B[i]번 아이에게 칭찬을 해준다. (i = 1,2,...,m) 이미 기분이 안좋아진 아이에게 칭찬을 해줘도 아이는 기분이 좋아지지 않는다. 1일부터 m일까지 각 날마다 기분이 좋은 아이의 수를 구하고자 한다. 0일차에는 모든 아이에게 칭찬을 해줘서 기분이 좋은 상태라고 가정한다. 예를 들어 4명의 아이는 2일, 3일, 1일, 2일 이내에 칭찬을 들어야한다. 선생님이 6일 동안 3번, 1번, 2번, 1번, 4번, 1번 아이에게 칭찬을 해줬다. 1일차에는 3번 아이에게 칭찬을 해줬다. 2일차에는 1번 아이에게 칭찬을 해줬는데, 2일 이내에 칭찬을..
16958번: 텔레포트 (acmicpc.net) 16958번: 텔레포트 2차원 평면 위에 N개의 도시가 있다. 일부 도시는 특별한 도시이다. (r1, c1)에 있는 도시에서 (r2, c2)에 있는 도시로 가는 이동 시간은 |r1 - r2| + |c1 - c2|와 같다. 만약, 두 도시가 특별한 도시라면, 텔 www.acmicpc.net 이 문제에서 다음과 같이 제출하면.. 시간 초과로 통과하지 못한다 from sys import stdin INF = 1e9 def floyd(graph,city): for k in range(1,n+1): for a in range(1,n+1): if k == a: continue for b in range(1,n+1): if a == b: continue graph[a]..
1. 문제 [3, 6, 2, 6, 7, 5, 2] 와 같이 숫자들이 주어졌을 때, 다음 질의에 대해 답하는 프로그램을 작성해보세요. 단, 질의마다 하나의 숫자가 주어지며 해당 번째 숫자를 제외한 다른 숫자들에 대해 인접한 숫자간의 차이의 합을 구해야 합니다. 예를 들어 질의로 5가 주어졌다면 5번째 숫자인 7을 제외한 다른 숫자들을 나열하면 [3, 6, 2, 6, 5, 2]가 되므로 인접한 숫자간의 차이의 합은 |3 - 6| + |6 - 2| + |2 - 6| + |6 - 5| + |5 - 2| = 15가 됩니다. 이때 주어지는 숫자는 1초과 N 미만임을 가정해도 좋습니다. -------------------------------------------------------------------------..
딥러닝/머신러닝, 통계학, IT프로그래밍, 알고리즘을 좋아하는 사람 https://github.com/yundaehyuck
