본문 바로가기

Programming

 (110)
[백준 1238번] 파티 link : https://www.acmicpc.net/problem/1238 파티 성공한국어 시간 제한메모리 제한제출정답맞은 사람정답 비율1 초128 MB68602826192340.587%문제N개의 숫자로 구분된 각각의 마을에 한 명의 학생이 살고 있다.어느 날 이 N명의 학생이 X (1 ≤ X ≤ N)번 마을에 모여서 파티를 벌이기로 했다. 이 마을 사이에는 총 M개의 단방향 도로들이 있고 i번째 길을 지나는데 Ti(1 ≤ Ti ≤ 100)의 시간을 소비한다.각각의 학생들은 파티에 참석하기 위해 걸어가서 다시 그들의 마을로 돌아와야 한다. 하지만 이 학생들은 워낙 게을러서 최단 시간에 오고 가기를 원한다.이 도로들은 단방향이기 때문에 아마 그들이 오고 가는 길이 다를지도 모른다. N명의 학생들 중 오..
[백준 6497번] 전력난 link : https://www.acmicpc.net/problem/6497 전력난 성공한국어 시간 제한메모리 제한제출정답맞은 사람정답 비율1 초128 MB130646832732.766%문제성진이는 한 도시의 시장인데 거지라서 전력난에 끙끙댄다. 그래서 원래 모든 길마다 켜져 있던 가로등 중 일부를 소등하기로 하였다. 길의 가로등을 켜 두면 하루에 길의 미터 수만큼 돈이 들어가는데, 일부를 소등하여 그만큼의 돈을 절약할 수 있다.그러나 만약 어떤 두 집을 왕래할 때, 불이 켜져 있지 않은 길을 반드시 지나야 한다면 위험하다. 그래서 도시에 있는 모든 두 집 쌍에 대해, 불이 켜진 길만으로 서로를 왕래할 수 있어야 한다.위 조건을 지키면서 절약할 수 있는 최대 액수를 구하시오.입력입력은 여러 개의 테스트..
[백준 1774번] 우주신과의 교감 link : https://www.acmicpc.net/problem/1774 우주신과의 교감 성공한국어 시간 제한메모리 제한제출정답맞은 사람정답 비율2 초128 MB90627716427.517%문제황선자씨는 우주신과 교감을 할수 있는 채널러 이다. 하지만 우주신은 하나만 있는 것이 아니기때문에 황선자 씨는 매번 여럿의 우주신과 교감하느라 힘이 든다. 이러던 와중에 새로운 우주신들이 황선자씨를 이용하게 되었다.하지만 위대한 우주신들은 바로 황선자씨와 연결될 필요가 없다. 이미 황선자씨와 혹은 이미 우주신끼리 교감할 수 있는 우주신들이 있기 때문에 새로운 우주신들은 그 우주신들을 거쳐서 황선자 씨와 교감을 할 수 있다.우주신들과의 교감은 우주신들과 황선자씨 혹은 우주신들 끼리 이어진 정신적인 통로를 통해 ..
[백준 2166번] 다각형의 면적 link : https://www.acmicpc.net/problem/2166 다각형의 면적 성공시간 제한메모리 제한제출정답맞은 사람정답 비율2 초128 MB329675148522.611%문제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 CCW 알고리즘 분류에..
[백준 11758번] CCW link : https://www.acmicpc.net/problem/11758 CCW 성공시간 제한메모리 제한제출정답맞은 사람정답 비율1 초256 MB23241618137073.616%문제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, 시계 방향이면 ..
CCW(CounterClockWise) 알고리즘 1. 개념 CCW는 외적을 이용해서 점 3개의 방향성을 나타내는 알고리즘이다. 즉, 세 점으로 이루어진 삼각형의 면적을 구하는 방법을 이용해서 방향성을 구한다. 우선 점 3개로 나타날 수 있는 경우는 총 3가지이다. 시계 방향, 일직선 방향, 반시계 방향 총 3가지이다. 2. 구현 어떠한 경우인지 알기 위해서 다음과 같은 식을 세운다. 여기서 S의 부호에 따라 경우를 3가지로 파악한다. 1) S > 0 : 반시계 방향 2) S = 0 : 일직선 3) S < 0 : 시계 방향 1234567891011int ccw(int x1, int y1, int x2, int y2, int x3, int y3) { int temp = x1*y2+x2*y3+x3*y1; temp = temp - y1*x2-y2*x3-y3*..
[백준 1912번] 연속합 link : http://link : https://www.acmicpc.net/problem/1912 연속합 성공시간 제한메모리 제한제출정답맞은 사람정답 비율2 초128 MB338869081630026.915%문제n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 숫자를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 숫자는 한 개 이상 선택해야 한다.예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다.입력첫째 줄에 정수 n(1≤n≤100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000..
[백준 14728번] 벼락치기 link : https://www.acmicpc.net/problem/14728 벼락치기 성공시간 제한메모리 제한제출정답맞은 사람정답 비율2 초256 MB108238330035.672%문제ChAOS(Chung-ang Algorithm Organization and Study) 회장이 되어 일이 많아진 준석이는 시험기간에도 일 때문에 공부를 하지 못하다가 시험 전 날이 되어버리고 말았다. 다행히도 친절하신 교수님께서 아래와 같은 힌트를 시험 전에 공지해 주셨다. 내용은 아래와 같다.여러 단원을 융합한 문제는 출제하지 않는다.한 단원에 한 문제를 출제한다. 단, 그 단원에 모든 내용을 알고 있어야 풀 수 있는 문제를 낼 것이다.이런 두가지 힌트와 함께 각 단원 별 배점을 적어 놓으셨다. 어떤 단원의 문제를 ..

티스토리툴바