중점 및 문제 이해 원형으로 생긴 원탁에 n개의 접시가 있다. 해당 접시에는 각각 숫자가 적혀있다. 이때 최소한으로 연결을 끊어서 오름차순으로 정렬된 배열을 만들려고 한다. 따라서 어디서 원탁의 연결을 끊는지가 중요한 부분이다. 또한 원이라는 특성 상 배열에 저장하는 경우 n번째 저장되는 값과 0번째 저장하는 값을 같게 하여서 흐름을 이어야한다. n, n+1에 대해서 n에 저장된 값이 n+1보다 크다면 연결을 끊고 count를 +1을 한다. 해당 작업으로 인해서 배열의 수를 알 수 있다. 정답 코드 #include using namespace std; int a[1000002]; int main(void){ ios::sync_with_stdio(0); cin.tie(0); int n; int count ..
coding-test
중점 및 문제 이해 n명의 학생들이 견학을 간다. 이때 2명씩 짝을 지어서 팀으로 만든다. 각 학생들은 능력치를 가지고 있는데 각 팀의 능력치의 합은 주어지는 m이라는 능력치 이상이여야 한다. 최대로 팀을 만들어서 보내는 경우 몇팀을 보낼 수 있는지 출력해야한다. 해당 학생들의 능력치는 각각 다를 것이다. 그렇다면 최대한으로 팀을 만들려면 가장 최소의 점수와 최대의 점수가 결합해야한다. m이란 점수를 넘기기 위해서는 최대값이 최소값보다 가지는 기대치가 크다고 생각한다. 또한 최소값을 최대랑 엮었음에도 팀이 만들어지지 않는다면 해당 최소값은 절대 사용하지 못하는 값이라고 생각했다. 따라서 입력받은 값을 sort한 후 각 끝에서 하나씩 비교하며 팀이 만들어지는지 아닌지를 판단하여서 제외한다. 이때 최솟값을 ..
중점 및 문제 이해 주어진 n일 안에서 최대한 연속되게 문제를 풀어야하는 것이 핵심이다. 이때 문제를 풀지 않은 날을 커버 할 수 있는 스트릭 프리즈를 사용할 수 있다. 0.99당 1개로 취급하며 최대 2개까지 사용 가능하다. 스트릭 프리즈는 사용하고 싶은 날에 사용한다. 위의 조건들을 만족하면서 문제를 푸는 날의 최대 유지 일수 와 문제를 최대로 많이 푼 개수를 출력한다. DP 알고리즘을 이용해서 문제를 풀이한다. 행렬을 이용해서 dp[n][0], [n][1], [n][2]로 각각 스트릭 프리즈를 사용한 개수를 의미한다. 문제를 푼 날이면 n-1에서 +1을 저장한다. 해당 날에는 스트릭 프리즈를 사용하지 않기에 0, 1, 2에서 각각 +1을 한 값을 더한다. 문제를 풀지 않은 날이면 1, 2에 대해서만..
중점 1. 중복 값 지우기 2. iterator 사용하여 숫자 세기 c++에서 지원하는 함수들을 사용하여서 문제를 해결할 수 있다. sort,unique, erase, lower_bound, begin, end를 사용한다. 위 문제를 풀기 위해서 vector를 사용하였다. sort 함수는 벡터의 요소들을 오름차순으로 정리한다. unique 함수는 해당 벡터에서 중복되는 값을 찾아서 해당 값들을 벡터의 끝으로 보낸다. 이때 해당 값들이 있었던 공백은 이후 순서의 값들이 순차적으로 채운다. 이후 옮겨진 요소들 중 첫번째 요소의 주소 값을 반환한다. erase 함수는 매개변수로 시작 주소와 끝나는 주소를 받습니다. 해당 주소에 요소들을 삭제합니다. lower_bound는 해당 값을 처음으로 초과하는 값의 주소..
중점 1. 나누어진 시험지 그룹들 중 가장 최소값이 시험 점수가 된다. 2. 그룹 간의 차이가 가장 적어야지만 최소값이 최댓값이 될 수 있다. 3. n이라는 점수 기준으로 그룹의 개수가 만족이 된다면 n은 시험 점수가 된다. 4. 그룹에 들어가는 시험지의 개수는 무관하다. n개의 그룹으로 시험지를 나누어서 n개의 그룹 중 가장 최솟값이 시험 점수가 된다. 그렇다면 n개의 그룹 간에 차이가 적어야지 가장 최대의 시험 점수를 받을 수 있을 것이다. 어떻게 하면 그룹들 간의 시험 점수의 차이가 적게 날 것인가? 그룹들은 순서대로 나누어지기 때문에 한 그룹을 나누는 기준 점수가 중요하다. 따라서 받을 수 있는 점수를 파마메트릭 서치를 통해서 찾아야 할 것이다. k라는 점수에 n개의 그룹이 나누어진다면 k는 최소..
중점 1. 주어진 과자의 길이 내에서 최대값을 찾아야한다. 2. 주어진 범위 내에서 조건을 만족하는 최대값을 탐색한다. 전형적인 파라메트릭 서치 문제이다. 범위 내에서 가능한 최대값 탐색하는 것이다. 최대 or 최소 문제를 찾는 과정 중 범위가 넓고 조건이 있다면 파라메트릭 서치를 의심해 봄직하다. 이분 탐색을 이용하는 경우 n이 조건에 부합하는지 하지 않는지에 따라서 이분 탐색에 이용되는 범위를 줄여가면서 찾는다. 정답 코드 #include using namespace std; int ans; int m, n, maxi; int a[1000005]; int main(void){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> m >> n; for (..
