알고리즘 문제풀이

백준 13549번 - 숨바꼭질 3 시간제한 메모리 제한 제출 정답 맞은 사람 정답 비율 2 초 512 MB 19622 5890 3680 26.760% 문제 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 0초 후에 2*X의 위치로 이동하게 된다. 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오. 입력 첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진..

백준 1082번 - 방 번호 시간제한 메모리 제한 제출 정답 맞은 사람 정답 비율 2 초 128 MB 1417 341 272 26.129% 문제 이번에 VIP 회장으로 새로 부임한 백은진은 빅뱅의 위대함을 세계에 널리 알리기 위해서 사무실을 하나 임대했다. 빅뱅은 위대하기 때문에, 사무실의 번호도 되도록이면 커야 한다고 생각한다. 따라서 지금 가지고 있는 돈 전부를 가지고 방 번호를 만들려고 한다. 1층에 있는 문방구에서는 숫자를 판다. 각 숫자의 가격은 서로 다를 수 있기 때문에, 현재 가지고 있는 돈을 이용해서 만들 수 있는 가장 큰 숫자를 만들려고 한다. 예를 들어, 문방구에서 파는 숫자가 0, 1, 2이고, 각 숫자의 가격이 6, 7, 8이고, 백은진이 현재 가지고 있는 돈이 21이라면, 백은진이..

정의 Counter-Clockwise 알고리즘은, 벡터의 외적을 통해서 한 정점을 기준으로 나머지 2개의 정점의 위치 관계를 파악하는 알고리즘이다. 벡터의 외적? ${\vec{a}}$ x ${\vec{b}}$ 는 다음과 같이 정의된다. ( ${\mid{\vec{a}} \mid}$ ${\mid{\vec{b}} \mid}$ ${\sin\theta}$) $\vec{v}$, [v는 a,b의 법선벡터, $\theta$는 a벡터에서 b벡터까지 반시계 방향으로 잰 각의 크기] 각의 크기 $\theta$는 180도인 $\pi$ 이하의 각도. (약 더 큰 각도라면 각의 변환을 통해서 ${0 \leq \theta \leq \pi}$ 내로 변환을 해주어야한다.) 또한 벡터의 평행이동을 활용하면 세 점의 좌표를 통해서 바로 ..

백준 2166번 - 다각형의 면적 시간제한 메모리 제한 제출 정답 맞은 사람 정답 비율 2 초 128 MB 11944 3025 2067 23.451% 문제 2차원 평면상에 N(3 ≤ N ≤ 10,000)개의 점으로 이루어진 다각형이 있다. 이 다각형의 면적을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N이 주어진다. 다음 N개의 줄에는 다각형을 이루는 순서대로 N개의 점의 x, y좌표가 주어진다. 좌표값은 절댓값이 100,000을 넘지 않는 정수이다. 출력 첫째 줄에 면적을 출력한다. 면적을 출력할 때에는 소수점 아래 둘째 자리에서 반올림하여 첫째 자리까지 출력한다. 예제 입력 1 4 0 0 0 10 10 10 10 0 예제 출력 1 100.0 출처 www.acmicpc.net/problem/2166..

백준 1495번 - 기타리스트 시간제한 메모리 제한 제출 정답 맞은 사람 정답 비율 2 초 128 MB 11381 3966 3073 34.057% 문제 Day Of Mourning의 기타리스트 강토는 다가오는 공연에서 연주할 N개의 곡을 연주하고 있다. 지금까지 공연과는 다른 공연을 보여주기 위해서 이번 공연에서는 매번 곡이 시작하기 전에 볼륨을 바꾸고 연주하려고 한다. 먼저, 공연이 시작하기 전에 각각의 곡이 시작하기 전에 바꿀 수 있는 볼륨의 리스트를 만들었다. 이 리스트를 V라고 했을 때, V[i]는 i번째 곡을 연주하기 전에 바꿀 수 있는 볼륨을 의미한다. 항상 리스트에 적힌 차이로만 볼륨을 바꿀 수 있다. 즉, 현재 볼륨이 P이고 지금 i번째 곡을 연주하기 전이라면, i번 곡은 P+V[i]나 P..

백준 11437번 - LCA 시간제한 메모리 제한 제출 정답 맞은 사람 정답 비율 3 초 256 MB 9137 4169 2408 44.659% 문제 N(2 ≤ N ≤ 50,000)개의 정점으로 이루어진 트리가 주어진다. 트리의 각 정점은 1번부터 N번까지 번호가 매겨져 있으며, 루트는 1번이다. 두 노드의 쌍 M(1 ≤ M ≤ 10,000)개가 주어졌을 때, 두 노드의 가장 가까운 공통 조상이 몇 번인지 출력한다. 입력 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정점 쌍이 주어진다. 출력 M개의 줄에 차례대로 입력받은 두 정점의 가장 가까운 공통 조상을..