joseph0528 코딩 블로그

문제 설명이 이게 다인 문제 설명은 간단한 문제이다. 이 문제를 처음 볼 때 이상한 수학으로 풀어야 되는 건가 싶을 수 있지만 사실 세그를 사용해서 풀 수 있다. 일단 |p [i]-p [j]| 를 1번이라고 하고 |q [i]-q [j]| 를 2번이라고 하겠다. 이 문제는 1번과 2번 중 작은 값을 골라야 하기 때문에 1번이 작은 경우와 2번이 작은 경우 이렇게 2개로 나눌 수 있다. 1번이 작거나 같은 경우부터 생각해보자. 1번이 작거나 같을려면 (j = p[j] 일때 p[i] < p[j] 일때 p[i]-p[j]

https://www.acmicpc.net/problem/2405 2405번: 세 수, 두 M n개의 정수 A[1], A[2], …, A[n]이 있다. 서로 다른 세 정수 i, j, k에 대해서 a = A[i], b = A[j], c = A[k]라 하자. 세 수의 중위(Median)값은 정렬했을 때 가운데에 오는 수가 된다. 세 수의 평균(Mean)값은 (a+b+c) www.acmicpc.net 생각보다 간단한 문제다 평균과 중윗값의 차가 최대한 크게 하려면 일정한 중윗값에 대해서 평균이 최대한 크거나 작을 때의 차 중 가장 큰 차를 구하면 된다. 값을 정렬했을때 양끝 값은 중윗값이 될 수 없으니 제외해주고 1~n-1에서 i번째 값이 중위 값이라고 했을 때 평균값이 가장 작게 나오게 하려면 i번째 값+i..

solved.ac 티어 : 플5 https://www.acmicpc.net/problem/22348 22348번: 헬기 착륙장 각 테스트 케이스에 대해, 한 줄에 하나씩, 빨강 페인트 a통과 파랑 페인트 b통만을 이용해 만들 수 있는 서로 다른 헬기 착륙장의 수를 109 + 7로 나눈 나머지를 출력한다. www.acmicpc.net 이문제는 dp 문제있은데 dp인걸 알기 어렵다고 한다 이 문제는 빨강 페인트 a와 파랑 페인트 b 이렇게 두 개가 입력으로 들어오면 이 두 개의 양을 넘지 않는 선에서 만들 수 있는 모든 착륙장의 경우의 수를 출력하는 문제이다. k개의 동심원인 착륙장을 만든다고 했을 때 k번째 동심원을 파랑 페인트를 칠한다고 하면 파랑 페인트는 b-k가 되고 남은 k-1개의 동심원은 a와 b..

solved.ac 티어 : 골드 2 www.acmicpc.net/problem/7894 7894번: 큰 수 많은 어플리케이션은 매우 큰 수를 사용한다. 이러한 어플리케이션은 데이터를 안전하게 전송하고, 암호화하기 위해서 수를 키로 사용한다. 수가 주어지면, 그 수의 팩토리얼의 자리수를 구하 www.acmicpc.net 이문제는 log10(1)+log10(2)+log10(3)... log10(m) 이 답인데 처음에 그냥 2중 반복으로 하면 시간 초과 날 거 같아서 log10(1)+log10(2)+log10(3)... log10(m) = log10(m!)인걸 이용해서 팩토리얼을 최대한 짧게 구해서 하려고 했지만 O(M/2)만큼 걸려 시간 초과가 나서 그냥 2중 반복으로 했더니 맞았다;; import math..