L.O.K

2212번: 센서 첫째 줄에 센서의 개수 N(1 ≤ N ≤ 10,000), 둘째 줄에 집중국의 개수 K(1 ≤ K ≤ 1000)가 주어진다. 셋째 줄에는 N개의 센서의 좌표가 한 개의 정수로 N개 주어진다. 각 좌표 사이에는 빈 칸이 하나 있 www.acmicpc.net ◎ 문제풀이 집중국에서 고속도로 위 센서를 관리할 때, 집중국이 관리할 수 있는 센서간 거리의 합의 최소값을 구하는 문제이다. 센서간 거리의 합이 최소가 되려면 두 개의 센서 사이의 거리가 가장 큰 곳을 기준으로 나누면 된다. 7개의 센서를 2개의 집중국으로 나눈다고 한다면, 센서3과 센서6 사이가 최대이므로 두 세선 사이를 기준으로 영역을 나눈다. 그러면 두개의 집중국이 관리하는 수신 가능한 영역의 거리의 합이 최소가 된다. ◎ 코드 ..

https://www.acmicpc.net/problem/18310 18310번: 안테나 첫째 줄에 집의 수 N이 자연수로 주어진다. (1≤N≤200,000) 둘째 줄에 N채의 집에 위치가 공백을 기준으로 구분되어 1이상 100,000이하의 자연수로 주어진다. www.acmicpc.net ◎ 문제풀이 안테나를 어느 집에 설치해야 [ 안테나 - 집 ] 거리의 합이 최소가 되는 지를 묻는 문제이다. 집은 { 1 , 5 , 9 , 9 , 9 , 11 } 에 주어졌다고 가정하자. 안테나의 위치를 x라고 한다면, sum = [ x - 1 ] + [ x - 5 ] + [ x - 9 ] + [ x - 9 ] + [ x - 9 ] + [ x - 11 ] sum의 최솟값을 구하는 문제이다. 안테나가 양 끝에 있으면 안테..

1744번: 수 묶기 길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 www.acmicpc.net ◎ 문제풀이 수열의 수는 음수 , 0, 양수가 가능하고 두개의 수를 묶어 곱한 뒤 합하는게 가능하다. 이때의 최대값을 구하는 문제이다. 합이 최대가 나오려면 음수와 양수는 분리되어야 한다. 음수와 양수의 곱은 음수가 나오기 때문이다. - 음수인 경우 1) 절대값이 큰값끼리 곱해야 한다. 2) 곱할 음수가 없는 음수는 0과 곱하여 상쇄되어야 한다. 3) 0도 없으면 그대로 음수를 합해야 한다. - 양수인 경우 1) 절대값이 큰값끼리 곱해야 한다. 2) 1은 곱셈..

https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net ◎문제풀이 규칙을 발견하면 쉬운 문제이다. '-' 연산이 나오면, 이후 나오는 수를 모두 괄호 안에 넣으면 괄호 안 모든 연산이 빼기가 된다. 수식이 나오면 수학으로 단순화하려는 시도가 중요한 문제였다. ◎코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; //BOJ1541..

https://www.acmicpc.net/problem/2109 2109번: 순회강연 한 저명한 학자에게 n(0 ≤ n ≤ 10,000)개의 대학에서 강연 요청을 해 왔다. 각 대학에서는 d(1 ≤ d ≤ 10,000)일 안에 와서 강연을 해 주면 p(1 ≤ p ≤ 10,000)만큼의 강연료를 지불하겠다고 알려왔다. www.acmicpc.net ◎ 문제풀이 위 문제는 d일 안에 강연을 해야함이 관건이다. 5일 안에 강연을 해야함의 의미는 1~5일 사이에 강연을 해야한다는 의미이다. 그래서 처음에는 일수를 기준으로 일수마다 강연이 가능한 것 중에 최대값을 넣으려고 했다. 그랬더니 자료구조를 많이 생성해야하고 조건이 복잡해졌다. 일수가 아닌 강연을 기준으로 하면 문제가 풀린다. 강연을 하나씩 가져와서 스케..

https://www.acmicpc.net/problem/1202 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net ◎문제풀이 보석이 N개 있고 가방이 K개 있을 때, 가방에 보석을 담을 수 있는 최대가격을 구하는 문제이다. ( 단, 가방 안에는 하나의 보석만 담을 수 있다. ) 처음에는 N개의 보석을 내림차순으로 정렬하고 가방K개를 오름차순을 정렬하여, 보석의 무게에 맞는 가방을 탐색하려고 했다. 그러나 이는 시간복잡도가 O(N*K)이고 N과 K는 ..

https://www.acmicpc.net/problem/2138 2138번: 전구와 스위치 N개의 스위치와 N개의 전구가 있다. 각각의 전구는 켜져 있는 상태와 꺼져 있는 상태 중 하나의 상태를 가진다. i(1 < i < N)번 스위치를 누르면 i-1, i, i+1의 세 개의 전구의 상태가 바뀐다. 즉, 꺼져 www.acmicpc.net ◎ 문제풀이 이 문제는 어렵게 느껴진다. 현재를 목표로 만드는데 한 개의 스위치가 여러 개의 전구에 영향을 주어, 경우를 복잡하게 만들기 때문이다. n번 스위치를 눌러 n번 전구를 목표와 일치시켰는데, n+1 스위치가 눌리면 다시 원위치이다. 그러므로 위 문제는 복잡하게 얽힌 경우를 얼마나 단순히 풀어낼 수 있는가를 묻는 문제이다. 경우를 나누어 보자. 1) 첫 번째 ..

https://www.acmicpc.net/problem/1080 1080번: 행렬 첫째 줄에 행렬의 크기 N M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 행렬 A가 주어지고, 그 다음줄부터 N개의 줄에는 행렬 B가 주어진다. www.acmicpc.net ◎문제풀이 아직 그리디 문제풀이의 감이 부족한것 같다. 최솟값을 구하는 문제라 두 행렬의 차이가 가장 많이 나는 좌표를 추출하여 3X3행렬을 뒤집는 방법으로 풀이를 시도했다. 그런데 이 문제는 그냥 좌표를 차례대로 확인하면서 틀린부분이 있으면 3x3행렬을 뒤집으면 되었다. 현재를 기준으로 최적해를 구하는 것이 그리디 문제이다. 전체에서 가장 많이 차이나는 좌표를 구하여 문제를 푸는 것이 아니다. ◎코드 #BOJ..

https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net ◎ 문제풀이 한 개의 회의실을 최대로 이용할 수 있는 회의의 개수를 구하는 문제이다. 끝나는 시간이 기준이다. 회의가 언제 끝나는지를 알아야 무엇을 시작할지가 결정된다. 그러므로 가장 빨리 끝나는 것부터 하나씩 회의실을 잡으면 된다. 그래서 정렬을 활용하여 문제를 풀었더니 한 가지 반례가 있었다. 2 9 9 1 9 끝나는 시간을 기준으로 하면 위 반례를 커버하지 못한다. 둘 다 똑같이 9시에 끝나지만 시작시간이 다르다. 그러므로 아래와 같이 풀면 된다. 1) 시작시간으로 먼저 정렬한다. 시작시간으로 정렬하면 같은..

◎ 문제 어떠한 수 N이 1이 될 때까지 다음의 두 과정 중 하나를 반복적으로 선택하여 수행하려고 한다. 단, 두번째 연산은 N이 K로 나누어떨어질 때만 선택할 수 있다. 1. N에서 1을 뺀다. 2. N을 K로 나눈다. 예를 들어 N이 17, K가 4라고 가정하자. 이때 1번의 과정을 한 번 수행하면 N은 16이 된다. 이후에 2번의 과정을 두 번 수행하면 N은 1이 된다. 결과적으로 이 경우 전체 과정을 실행한 횟수는 3이 된다. 이는 N을 1로 만드는 최소 횟수이다. N과 K가 주어질 때 N이 1이 될 때까지 1번 혹은 2번의 과정을 수행해야 하는 최소 횟수를 구하는 프로그램을 작성하시오. - 입력조건 첫째 줄에 N(2≤ N ≤ 100,000)과 K(2≤ K ≤ 100,000)가 공백으로 구분되며 ..