어흥

문제 링크: www.acmicpc.net/problem/9879 9879번: Cross Country Skiing The cross-country skiing course at the winter Moolympics is described by an M x N grid of elevations (1 = 0 && nx row >> col; int l = 0, r = 0, mid, result; for (int i = 0; i > arr[i][j]; r = max(r, arr[i][j]); } for (int i = 0; i ..

문제 링크: www.acmicpc.net/problem/2166 2166번: 다각형의 면적 첫째 줄에 N이 주어진다. 다음 N개의 줄에는 다각형을 이루는 순서대로 N개의 점의 x, y좌표가 주어진다. 좌표값은 절댓값이 100,000을 넘지 않는 정수이다. www.acmicpc.net 1. 주의할 점 - 소수점으로 나타내야 하므로 Double을 사용하도록 한다(10^5*10^5 여러개를 더한 값은 Int의 범위를 벗어나므로 주의) 2. 구현 - 모든 좌표를 X[],Y[]에 입력받은 이후, Result를 0으로 설정한다 - Result+=CCW()의 결과값을 통해 다각형의 면적을 구한다(다각형을 이루는 순서대로 좌표가 주어진다고 적혀있음) #include #include using namespace std;..

문제 링크: www.acmicpc.net/problem/11758 11758번: CCW 첫째 줄에 P1의 (x1, y1), 둘째 줄에 P2의 (x2, y2), 셋째 줄에 P3의 (x3, y3)가 주어진다. (-10,000 ≤ x1, y1, x2, y2, x3, y3 ≤ 10,000) 모든 좌표는 정수이다. P1, P2, P3의 좌표는 서로 다르다. www.acmicpc.net (간단한 외적 설명은 imnotabear.tistory.com/324, 자세한 설명은 degurii.tistory.com/47 참조) 1. 주의할 점 - 외적을 이용한 삼각형의 넓이 구하기 공식을 통해 CCW를 구할 수 있도록 한다 2. 구현 - 3개의 좌표를 X[], Y[]배열에 입력 받는다 - BA, CA 반직선에 대한 벡터를 ..

문제 링크: www.acmicpc.net/problem/2170 2170번: 선 긋기 첫째 줄에 선을 그은 횟수 N(1≤N≤1,000,000)이 주어진다. 다음 N개의 줄에는 선을 그을 때 선택한 두 점이 주어진다. 선택한 지점은 -1,000,000,000 이상 1,000,000,000 이하의 정수이다. www.acmicpc.net 1. 주의할 점 - 왼쪽에 대한 오름차순으로 정렬 이후, 오른쪽에 대한 오름차순 정렬을 진행한다 - 입력 받을때, 처음 받는 수가 항상 왼쪽에 위치한다고 보장할 수 없다 2. 구현 - S(Start)에 대해서 오름차순으로 정렬 -> E(End)에 대해서 오름차순 정렬을 진행하는 우선순위큐를 생성한다 - 각 점에 대해서 입력받을 때, 작은 값을 S, 큰 값을 E에 할당한 이후 ..

문제 링크: www.acmicpc.net/problem/2116 2116번: 주사위 쌓기 첫줄에는 주사위의 개수가 입력된다. 그 다음 줄부터는 한 줄에 하나씩 주사위의 종류가 1번 주사위부터 주사위 번호 순서대로 입력된다. 주사위의 종류는 각 면에 적혀진 숫자가 그림1에 있는 www.acmicpc.net 1. 주의할 점 - 특정 면이 윗면일때(반대편도 동일) 옆면에 적힌 숫자의 값 중에서 최대값을 Maxi[][]에 저장해놓는다 - 가장 아래층이 정해지면 위는 경우의 수가 1가지 뿐이다(옆면의 최대값을 미리 구했기 때문) 2. 구현 - 주사위에 대한 정보를 Dice[] 벡터에 입력받는다 - 각 주사위 면이 윗면일때 옆면의 최대값을 Maxi[i번쨰 주사위][j번째 면(반대편 포함)]에 저장한다 - 가장 아래..

문제 링크: www.acmicpc.net/problem/12781 12781번: PIZZA ALVOLOC 입력의 첫 줄에는 도윤이와 친구들이 선택한 점의 좌표 x, y(-10,000 ≤ x, y ≤ 10,000)가 순서대로 4개 주어진다. x, y값은 항상 정수이다. www.acmicpc.net 1. 주의할 점 - 선분의 외적을 이용한 CCW에 대해 알고 있어야 한다(1->2->3의 순서로 갈 경우, S가 음수면 시계, 양수면 반시계방향) - S가 0인 경우를 처리한다 A: (x1, y1), B: (x2, y2), C: (x3, y3) -> A: (x1, y1, 1), B: (x2, y2, 1), C: (x3, y3, 1) -> 벡터 AB: (x2-x1, y2-y1, 0), 벡터 AC: (x3-x1, y..

문제 링크: www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n*n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서 www.acmicpc.net 1. 주의할 점 - 메모아이징 기법을 이용한다 - 값을 저장해서 사용하는 형태로 한다 2. 구현 - 모든 수를 입력 받고, Check[][] 배열에는 현재 지점에서 시작하여 살 수 있는 최대 일수를 저장한다 - 만약 Check[][] 값이 0이라면 DFS()를 수행한다 - DFS(y,x) 함수에는 이미 해당 Check[y][x] 값이 양수라면 해당 값을 반환한다. 0이라면, 현재 위치를 기..

문제링크: www.acmicpc.net/problem/14725 14725번: 개미굴 첫 번째 줄은 로봇 개미가 각 층을 따라 내려오면서 알게 된 먹이의 정보 개수 N개가 주어진다. (1 ≤ N ≤ 1000) 두 번째 줄부터 N+1 번째 줄까지, 각 줄의 시작은 로봇 개미 한마리가 보내준 먹이 www.acmicpc.net 1. 주의할 점 - 트리나 트라이에 대해서 알고 있어야 한다 - 사전순으로 출력해야한다(정렬된 무엇인가를 사용) 2. 구현 - Node 구조체를 만들어서 해당 Node의 Map을 생성하고, insert()와 print()의 기능을 하는 함수를 생성한다 - Node구조체 형태인 Root 노드를 처음에 만든다 - Insert() 함수는 입력받은 길을 저장하고 있는 V 벡터와 현재 개미굴의 ..