아롱이의 PS하는 블로그

[Python] 백준 4008 - 특공대

https://www.acmicpc.net/problem/4008문제1부터 n까지 번호가 붙여진 n명의 병사들로 이루어진 군대의 지휘관이 있다. 이 지휘관은 앞으로의 전투를 위하여 n명의 병사들을 여러 개의 특공대로 나누고자 한다. 결속력과 사기를 높이기 위하여 각 특공대는 {i, i+1, ..., i+k}형태의 번호가 연속하는 병사들로 구성된다.각 병사 i의 전투력은 xi이다. 병사들 {i, i+1, ..., i+k}로 구성된 특공대의 전투력 x는 원래는 각 병사의 전투력의 합으로 계산되었다. 달리 말하면 x = xi + xi+1 + ... + xk이었다.그러나 여러 해의 영광스러운 승리를 통하여 특공대의 전투력을 다음과 같이 조정해야 하는 것으로 결론을 내렸다: 특공대의 조정된 전투력 x′는 등식 x..

[Python] 백준 14751 - Leftmost Segment

https://www.acmicpc.net/problem/14751문제There are two distinct horizontal lines hupper and hlower in the xy-coordinate plane and n line segments connecting them. One endpoint of each segment lies on hupper and the other on hlower. All endpoints of the segments are distinct. All segments are numbered from 1 to n. Consider a horizontal line hi located between hupper and hlower, which will be given ..

[Python] 백준 13263 - 나무 자르기

https://www.acmicpc.net/problem/13263문제높이가 a1, a2, ..., an인 나무 n개를 전기톱을 이용해서 자르려고 한다.i번 나무에 전기톱을 사용할 때 마다 그 나무의 높이는 1만큼 감소한다. 전기톱은 사용할 때 마다 충전해야 한다. 전기톱을 충전하는 비용은 완전히 자른 나무의 번호에 영향을 받는다. 즉, 높이가 0이 되어버린 나무의 번호에 영향을 받는다. 완전히 잘려진 나무의 번호 중 최댓값이 i이면, 전기톱을 충전하는 비용은 bi이다. 완전히 잘려진 나무가 없다면 전기톱은 충전할 수가 없다. 가장 처음에 전기톱은 충전되어져 있다.나무의 높이 ai와 각각의 나무에 대한 충전 비용 bi가 주어졌을 때, 모든 나무를 완전히 자르는데 (높이를 0으로 만드는데) 필요한 충전 비..

https://www.acmicpc.net/problem/9892문제(직접 핵심만 번역해보겠음)2차원 평면 상에 점들이 여러개 주어진다. width w는 이 점들을 모두 감싸는 두 평행한 직선 사이의 최소 거리이다.예를 들면 다음 그림과 같다.당신은 주어진 점들에 대해서 w^2를 계산한 다음 이 수의 정수 부분만 출력하면 된다. 이 문제를 쉽게 풀게 하기 위해 공식을 하나 제공하겠다. 삼각형 ABC가 있어서 A(xa, ya), B(xb, yb), C(xc, yc)라고 할 때 이 삼각형의 높이 h는과 같이 계산될 수 있다. 여기서 문자 시그마의 값은 ABC가 반시계방향이면 1이고 시계방향이면 -1이다. Figure 2를 참고하라.모든 점들이 일직선에 놓여있다면, width는 0이 된다. 입력첫 번째 줄에는..

https://www.acmicpc.net/problem/10254문제n개의 도시를 가진 나라가 있다. 이 나라에서는 도시들 중 가장 먼 두 도시 사이에 직행 고속도로를 놓으려 한다.고속도로는 시작점과 끝점이 아닌 다른 나라를 통과해도 된다. 즉, n개의 도시 중 유클리드 거리가 가장 먼 두 도시를 찾으려 한다. 모든 도시는 한 평면 위에 있다.위의 예제에서는 (12,0)의 도시와 (-6,3)의 도시가 가장 먼 유클리드 거리를 갖는다.도시 n개의 좌표가 주어지면 모든 두 도시 쌍의 거리 중 가장 먼 두 도시를 찾아라.입력첫째 줄에 테스트 케이스의 수 T가 주어진다. 각 테스트 케이스의 첫 줄엔 도시의 개수 n이 주어진다. (2 ≤ n ≤ 200,000) 그 후 n줄에 걸쳐 각 도시의 x좌표와 y좌표가 주..

https://www.acmicpc.net/problem/1708 문제다각형의 임의의 두 꼭짓점을 연결하는 선분이 항상 다각형 내부에 존재하는 다각형을 볼록 다각형이라고 한다. 아래 그림에서 (a)는 볼록 다각형이며, (b)는 볼록 다각형이 아니다.조금만 생각해 보면 다각형의 모든 내각이 180도 이하일 때 볼록 다각형이 된다는 것을 알 수 있다. 편의상 이 문제에서는 180도 미만인 경우만을 볼록 다각형으로 한정하도록 한다.2차원 평면에 N개의 점이 주어졌을 때, 이들 중 몇 개의 점을 골라 볼록 다각형을 만드는데, 나머지 모든 점을 내부에 포함하도록 할 수 있다. 이를 볼록 껍질 (CONVEX HULL) 이라 한다. 아래 그림은 N=10인 경우의 한 예이다.점의 집합이 주어졌을 때, 볼록 껍질을 이루..

https://www.acmicpc.net/problem/11758 문제2차원 좌표 평면 위에 있는 점 3개 P1, P2, P3가 주어진다. P1, P2, P3를 순서대로 이은 선분이 어떤 방향을 이루고 있는지 구하는 프로그램을 작성하시오.입력첫째 줄에 P1의 (x1, y1), 둘째 줄에 P2의 (x2, y2), 셋째 줄에 P3의 (x3, y3)가 주어진다. (-10,000 ≤ x1, y1, x2, y2, x3, y3 ≤ 10,000) 모든 좌표는 정수이다. P1, P2, P3의 좌표는 서로 다르다.출력P1, P2, P3를 순서대로 이은 선분이 반시계 방향을 나타내면 1, 시계 방향이면 -1, 일직선이면 0을 출력한다. 풀이CCW 알고리즘은 주어진 세 점의 방향성을 판별하는 매우매우 유명한 알고리즘이다...

https://www.acmicpc.net/problem/1695 문제앞에서 뒤로 보나, 뒤에서 앞으로 보나 같은 수열을 팰린드롬 이라고 한다. 예를 들어 {1}, {1, 2, 1}, {1, 2, 2, 1}과 같은 수열은 팰린드롬 이지만, {1, 2, 3}, {1, 2, 3, 2} 등은 팰린드롬이 아니다.한 수열이 주어졌을 때, 이 수열에 최소 개수의 수를 끼워 넣어 팰린드롬을 만들려고 한다. 최소 몇 개의 수를 끼워 넣으면 되는지를 알아내는 프로그램을 작성하시오.입력첫째 줄에 수열의 길이 N(1≤N≤5,000)이 주어진다. 다음 줄에는 N개의 수열을 이루는 수들이 주어진다. 각 수들은 int 범위이다.출력첫째 줄에 끼워 넣을 수들의 최소 개수를 출력한다. 풀이dp 문제이다.dp 문제라면 본디, 하나의 ..

https://www.acmicpc.net/problem/21133 문제N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.N이 주어졌을 때, 퀸을 놓는 방법 한 가지를 출력하는 프로그램을 작성하시오.입력첫째 줄에 N이 주어진다. (4 ≤ N ≤ 10,000)출력 N개의 줄을 출력해야 한다. i번째 줄에는 하나의 정수를 출력해야 하고, 이 정수는 i번째 행에 있는 퀸이 있는 열의 번호이다. 풀이예전에 N-Queen(3344)번에서 썼던 코드를 참고해보자. N = int(input())if N%2 == 0: #8, 26, 2012 if N%3 == 2: for i in range(1, N, 2): print(i+1) ..

https://www.acmicpc.net/problem/3344 문제8*8 체스보드에 8개의 퀸을 서로 공격하지 못하게 놓는 문제는 잘 알려져 있는 문제이다. 퀸은 같은 행, 열, 또는 대각선 위에 있는 말을 공격할 수 있다. 이 문제의 한가지 정답은 아래 그림과 같다.이 문제의 조금 더 일반화된 문제는 Franz Nauck이 1850년에 제기했다.N*N 보드에 N개의 퀸을 서로 다른 두 퀸이 공격하지 못하게 놓는 경우의 수는 몇 가지가 있을까?이 문제는 N>3인 경우에 경우의 수가 적어도 1개 라는 것이 증명되어 있다. 예를 들어, N=26인 경우에 22317699616364044가지 방법이 있다.N이 주어졌을 때, N*N 보드에 N개의 퀸을 서로 다른 두 퀸이 공격하지 못하게 놓는 한가지 경우를 출..