mojo's Blog

문제 링크 : 2343번: 기타 레슨 (acmicpc.net) 2343번: 기타 레슨 강토는 자신의 기타 강의 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 강의가 들어가는데, 블루레이를 녹화할 때, 강의의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경 www.acmicpc.net 문제 강토는 자신의 기타 강의 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 강의가 들어가는데, 블루레이를 녹화할 때, 강의의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경우에는 강의의 흐름이 끊겨, 학생들이 대혼란에 빠질 수 있기 때문이다. 즉, i번 강의와 j번 강의를 같은 블루레이에 녹화하려면 i와 j 사이의 모든 강의도 같은 블루레이에 녹화해야 한다. 강토는 이 블루레이가 얼마나 ..

문제 링크 : 2776번: 암기왕 (acmicpc.net) 2776번: 암기왕 연종이는 엄청난 기억력을 가지고 있다. 그래서 하루 동안 본 정수들을 모두 기억 할 수 있다. 하지만 이를 믿을 수 없는 동규는 그의 기억력을 시험해 보기로 한다. 동규는 연종을 따라 다니며, www.acmicpc.net 문제 연종이는 엄청난 기억력을 가지고 있다. 그래서 하루 동안 본 정수들을 모두 기억 할 수 있다. 하지만 이를 믿을 수 없는 동규는 그의 기억력을 시험해 보기로 한다. 동규는 연종을 따라 다니며, 연종이 하루 동안 본 정수들을 모두 ‘수첩1’에 적어 놓았다. 그것을 바탕으로 그가 진짜 암기왕인지 알아보기 위해, 동규는 연종에게 M개의 질문을 던졌다. 질문의 내용은 “X라는 정수를 오늘 본 적이 있는가?” 이..

문제 링크 => 2737번: 연속 합 (acmicpc.net) 2737번: 연속 합 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 정수 하나로 이루어져 있다. 이 정수는 문제에서 설명한 N이며, 231보다 작다. www.acmicpc.net 알고리즘이 수학으로 분류되었지만 binary search 를 이용하여 해결했다. 문제는 굉장히 간단하다. 숫자 N 에 대하여 2개 이상의 연속하는 수의 합이 나올 수 있는 모든 경우의 수를 구하는 문제이다. 간단하게 생각해본다. 임의의 수 (x > 0) 에 대하여 다음과 같은 작업을 계속 해준다. (1) 연속하는 수 2개 ) x + (x + 1) = N 를 만족하는 x 가 있으면 경우의 수를 counting 한다. (2) 연속하는 수 3개 ) x..

문제 링크 => 12738번: 가장 긴 증가하는 부분 수열 3 (acmicpc.net) 12738번: 가장 긴 증가하는 부분 수열 3 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000) www.acmicpc.net 가장 긴 증가하는 부분 수열 2 문제에서 수열의 값이 커진것을 제외하고 동일한 문제이다. [백준 12015] 가장 긴 증가하는 부분 수열 2 :: M - J - C (tistory.com) [백준 12015] 가장 긴 증가하는 부분 수열 2 문제 링크 => 12015번: 가장 긴 증가하는 부분 수열 2 (acmicpc.net) 12015번: 가장 ..

문제 링크 => 12015번: 가장 긴 증가하는 부분 수열 2 (acmicpc.net) 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net 이 문제는 이분 탐색을 이용하는 문제이다. 이전에 해결하였던 문제를 동일하게 적용한다면 시간 초과가 난다. (n값이 1,000,000 으로 주어짐) vector v 를 활용하여 다음과 같은 방법으로 배열에 있는 값들을 push하도록 한다. 현재 벡터 v의 원소들에 대하여 arr[i] 값이 있는지를 lower_bound를 이용하여 구한다. lower_bound를 이용하여 얻어낸 ..

문제 링크 => 19637번: IF문 좀 대신 써줘 (acmicpc.net) 19637번: IF문 좀 대신 써줘 첫 번째 줄에는 칭호의 개수 N (1 ≤ N ≤ 105)과 칭호를 출력해야 하는 캐릭터들의 개수 M (1 ≤ M ≤ 105)이 빈칸을 사이에 두고 주어진다. (1 ≤ N, M ≤ 105) 두 번째 줄부터 N개의 줄에 각 칭 www.acmicpc.net 이분탐색 문제이다. 이문제에서 Input 은 n 개의 (string, long long) 형태로 주어지는데 long long 값이 오름차순으로 주어지는 것에 대해서 눈여겨 볼 필요가 있다. 즉, 벡터에다가 값을 push한 후에 정렬하는 operation을 하지 않고 바로 이분탐색을 할 수 있다는 것이 핵심이다. 풀이 code #define _CR..