문제 https://www.acmicpc.net/problem/2166 2166번: 다각형의 면적 첫째 줄에 N이 주어진다. 다음 N개의 줄에는 다각형을 이루는 순서대로 N개의 점의 x, y좌표가 주어진다. 좌표값은 절댓값이 100,000을 넘지 않는 정수이다. www.acmicpc.net 풀이 CCW 알고리즘 사용해서 해결한 문제이다. 세 점 A(x1, y1) B(x2,y2) C(x3,y3) 이 있을 때 삼각형의 넓이는 다음과 같다. 0.5(abs((x1y2 + x2y3 + x3y1) - (y1x2 + y2x3 + y3x1)) 이는 CCW 알고리즘의 결과에 0.5를 곱해준 것과 같다. 좌표 하나를 기준으로 삼각형을 만들어 각 삼각형의 합을 구해주면 된다. 코드 import java.io.Buffered..
[문제] https://www.acmicpc.net/problem/2143 2143번: 두 배열의 합 첫째 줄에 T(-1,000,000,000 ≤ T ≤ 1,000,000,000)가 주어진다. 다음 줄에는 n(1 ≤ n ≤ 1,000)이 주어지고, 그 다음 줄에 n개의 정수로 A[1], …, A[n]이 주어진다. 다음 줄에는 m(1 ≤ m ≤ 1,000)이 주어지고, 그 www.acmicpc.net [풀이] A에서 가능한 부분합을 모두 구하고 B에서 가능한 부분합을 모두 구한다. A의 부분합이 저장된 배열을 sum_a라고 하고, B의 부분합이 저장된 배열을 sum_b라고 했을 때, sum_a[i] = T - sum_b[j] 를 만족하는 i와 j값을 찾아야 한다. 단순하게 찾으면 메모리 초과 또는 시간 초..
[문제] https://www.acmicpc.net/problem/1644 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net [풀이] 투 포인터를 이용하면 쉽게 풀 수 있는 문제이다. 문제를 푸는 방법은 아래와 같다. 1. 조건 N의 범위가 (1 ≤ N ≤ 4,000,000) 이므로, (1 ≤ N ≤ 4,000,000) 사이의 소수를 미리 모두 구한다. 2. 연속된 소수의 합이므로, 연속된 소수의 합을 미리 구하여 배열에 저장을 해둔다. 3. 투 포인터를 이용하여, 풀어준다. 1번 과정은 에라토스테네스의 체를 이용하여 해결한다. prime = MutableList(MAX){true} prime[1] = false prime[0] ..
[문제] https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net [풀이] 문제의 조건은 다음과 같다. 1번 집의 색은 2번 집의 색과 같지 않아야 한다. N번 집의 색은 N-1번 집의 색과 같지 않아야 한다. i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다. 결국 i번째는 i-1째 집의 색과 같지 않으면 된다. 예를 들어 i번째 색상이 빨강이라면, i -1번째는 파랑 또는 초록이 와야 한다...
[문제] https://www.acmicpc.net/problem/17281 17281번: ⚾ ⚾는 9명으로 이루어진 두 팀이 공격과 수비를 번갈아 하는 게임이다. 하나의 이닝은 공격과 수비로 이루어져 있고, 총 N이닝 동안 게임을 진행해야 한다. 한 이닝에 3아웃이 발생하면 이닝이 종 www.acmicpc.net 주의 : 코틀린으로 풀 때, 베이스를 배열에 저장해놓고 풀게 되면, 시간초과가 발생합니다. [풀이] - 문제 설명 문제를 이해를 잘못해서 한 번 삽질하고, 시간초과 때문에 두 번 고생한 문제이다. 간단하게 요약을 하면, 입력값 N은 이닝 수 이다. 이닝 수는 야구로 생각하면 1회초, 1회말의 그 1회를 의미한다. 입력으로 들어온 이닝 수 만큼 경기를 진행했을 때, 얻을 수 있는 최고점을 기록하..
[문제] https://www.acmicpc.net/problem/15591 15591번: MooTube (Silver) 농부 존은 1번 동영상과 2번 동영상이 USADO 3을 가지고, 2번 동영상과 3번 동영상이 USADO 2를 가지고, 2번 동영상과 4번 동영상이 USADO 4를 가진다고 했다. 이것에 기반해서 1번 동영상과 3번 동영상의 www.acmicpc.net [풀이] bfs를 이용하여 풀었다. visit 배열을 만들어, 방문하지 않았으며 최소 K값을 넘어가는 값만 탐색을 해주었다. [코드] import java.io.BufferedReader import java.io.BufferedWriter import java.io.InputStreamReader import java.io.Output..
