백준 9655_돌 게임 시간 제한 1초, 메모리 제한 128MB # 조건 돌 게임은 두 명이서 즐기는 재밌는 게임이다. 탁자 위에 돌 N개가 있다. 상근이와 창영이는 턴을 번갈아가면서 돌을 가져가며, 돌은 1개 또는 3개 가져갈 수 있다. 마지막 돌을 가져가는 사람이 게임을 이기게 된다. 두 사람이 완벽하게 게임을 했을 때, 이기는 사람을 구하는 프로그램을 작성하시오. 게임은 상근이가 먼저 시작한다. 입력 첫째 줄에 N이 주어진다. (1 ≤ N ≤ 1000) 출력 상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY을 출력한다. 접근 방법 완벽하게 게임을 하기에 규칙을 찾는 것이 중요해 보였다. 1개 또는 3개를 가져갈 수 있는 상황에 마지막 돌을 가져가는 사람이 이기는 게임이다. 즉, 전체 돌의..

백준 2162-선분 그룹 시간 제한 2초, 메모리 제한 128MB # 조건 N개의 선분들이 2차원 평면상에 주어졌다. 선분은 양 끝점의 x, y좌표로 한다. 두 선분이 서로 만나는 경우, 두 선분은 같은 그룹에 속한다고 정의 그룹의 크기는 그 그룹에 속한 선분의 개수로 정의 두 선분이 주어졌을 때, 이 선분들은 총 몇 개의 그룹으로 되어있을까? 또, 가장 큰 그룹에 속한 선분의 개수는 몇 개일까? 입력 첫째 줄에 N(1 ≤ N ≤ 3,000)이 주어진다. 둘째 줄부터 N+1번째 줄에는 양 끝점의 좌표가 x1, y1, x2, y2의 순서로 주어진다. 각 좌표의 절댓값은 5,000을 넘지 않으며, 입력되는 좌표 사이에는 빈칸이 하나 있다. 출력 첫째 줄에 그룹의 수를, 둘째 줄에 가장 크기가 큰 그룹에 속한..

백준 17387_선분교차2 시간제한 0.25초(추가 시간 없음) 메모리제한 512MB # 조건 2차원 좌표 평면 위의 두 선분 L1, L2가 주어졌을 때, 두 선분이 교차하는지 아닌지 구해보자. 한 선분의 끝 점이 다른 선분이나 끝 점 위에 있는 것도 교차하는 것이다. L1의 양 끝 점은 (x1, y1), (x2, y2), L2의 양 끝 점은 (x3, y3), (x4, y4)이다 입력 첫째 줄에 L1의 양 끝 점 x1, y1, x2, y2가, 둘째 줄에 L2의 양 끝 점 x3, y3, x4, y4가 주어진다. 출력 L1과 L2가 교차하면 1, 아니면 0을 출력한다. 제한 -1,000,000 ≤ x1, y1, x2, y2, x3, y3, x4, y4 ≤ 1,000,000 x1, y1, x2, y2, x3,..

http://www.acmicpc.net/problem/13458 13458번: 시험 감독 첫째 줄에 시험장의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 각 시험장에 있는 응시자의 수 Ai (1 ≤ Ai ≤ 1,000,000)가 주어진다. 셋째 줄에는 B와 C가 주어진다. (1 ≤ B, C ≤ 1,000,000) www.acmicpc.net # 조건 제한시간 2초, 메모리 512MB 총 N개의 시험장이 있고, 각각의 시험장마다 응시자들이 있다. i번 시험장에 있는 응시자의 수는 Ai명이다. 감독관은 총감독관과 부감독관으로 두 종류가 있다. 총감독관은 한 시험장에서 감시할 수 있는 응시자의 수가 B명이고, 부감독관은 한 시험장에서 감시할 수 있는 응시자의 수가 C명이다. 각각의 시..

http://www.acmicpc.net/problem/2166 2166번: 다각형의 면적 첫째 줄에 N이 주어진다. 다음 N개의 줄에는 다각형을 이루는 순서대로 N개의 점의 x, y좌표가 주어진다. 좌표값은 절댓값이 100,000을 넘지 않는 정수이다. www.acmicpc.net # 조건 2차원 평면상에 N(3 ≤ N ≤ 10,000)개의 점으로 이루어진 다각형이 있다. 이 다각형의 면적을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N이 주어진다. 다음 N개의 줄에는 다각형을 이루는 순서대로 N개의 점의 x, y좌표가 주어진다. 좌표값은 절댓값이 100,000을 넘지 않는 정수이다. 출력 첫째 줄에 면적을 출력한다. 면적을 출력할 때에는 소수점 아래 둘째 자리에서 반올림하여 첫째 자리까지 출력한다..

http://www.acmicpc.net/problem/2568 2568번: 전깃줄 - 2 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100,000 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결 www.acmicpc.net # 조건 두 전봇대 A와 B 사이에 하나 둘씩 전깃줄을 추가하다 보니 전깃줄이 서로 교차하는 경우가 발생하였다. 합선의 위험이 있어 이들 중 몇 개의 전깃줄을 없애 전깃줄이 교차하지 않도록 만들려고 한다. 예를 들어, 과 같이 전깃줄이 연결되어 있는 경우 A의 1번 위치와 B의 8번 위치를 잇는 전깃줄, A의 3번 위치와 B의 9번 위치를 잇는 전깃줄, A의 4번 위치와 B의 1번 위치를 잇는 ..

http://wwww.acmicpc.net/problem/1007 # 조건 평면 상에 N개의 점이 찍혀있고, 그 점을 집합 P라고 하자. 집합 P의 벡터 매칭은 벡터의 집합인데, 모든 벡터는 집합 P의 한 점에서 시작해서, 또 다른 점에서 끝나는 벡터의 집합이다. 또, P에 속하는 모든 점은 한 번씩 쓰여야 한다. 벡터 매칭에 있는 벡터의 개수는 P에 있는 점의 절반이다. 평면 상의 점이 주어졌을 때, 집합 P의 벡터 매칭에 있는 벡터의 합의 길이의 최솟값을 출력하는 프로그램을 작성하시오. # 접근 방법 우선 벡터를 구하는 방법 v1 = (x2-x1, y2-y1) v2 = (x4-x3, y4-y3) 벡터 사이의 합은 v1 + v2 = (x2+x4 -x1-x3, y2+y4 -y1-y3) |v1 + v2| ..

http://www.acmicpc.net/problem/3096 3096번: 영화제 넓은 강이 있는 나라가 있다. 강의 왼쪽에는 마을이 N개, 오른쪽에도 N개가 있으며, 각 마을은 1번부터 N번까지 번호가 매겨져 있다. 왼쪽 마을 중 하나와 오른쪽 마을 중 하나를 연결하는 배는 총 www.acmicpc.net # 조건 강의 왼쪽, 오른쪽에는 N개의 망르이 있고 각 마을은 1번부터 N번까지 번호 왼쪽 마을 중 하나와 오른쪽 마을 중 하나를 연결하는 배는 총 M개가 있고, 양방향 연걸 상근이는 총 4개 마을에서 영화제를 개최하려고 한다. 왼쪽 마을에서 2개, 오른쪽 마을에서 2개를 고르며, 왼쪽 마을은 모두 오른쪽 마을과 배로 직접 연결되어 있어야 한다. 영화제를 개최할 마을을 고르는 방법의 수를 구하는 프..

http://www.acmicpc.net/problem/17087 17087번: 숨바꼭질 6 수빈이는 동생 N명과 숨바꼭질을 하고 있다. 수빈이는 현재 점 S에 있고, 동생은 A1, A2, ..., AN에 있다. 수빈이는 걸어서 이동을 할 수 있다. 수빈이의 위치가 X일때 걷는다면 1초 후에 X+D나 X-D로 이 www.acmicpc.net # 조건 동생 N명과 숨바꼭질 수빈이는 현재 점 S에 있고, 동생은 A1, A2 .. An 수빈이는 걸어서 이동을 할 수 있는데, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X+D나 X-D로 이동 가능 수빈이의 위치가 동생이 있는 위치와 같다면 동생을 찾았다고 한다. 모든 동생을 찾기 위해 D의 값을 정하는데 가능한 D의 최댓값을 구하여라. # 접근 방법 동생들의 ..