while(1) 작심삼일();

http://www.acmicpc.net/problem/11722 11722번: 가장 긴 감소하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10} www.acmicpc.net 풀이) 11055(가장 큰 증가 부분 수열)과 같은 문제이다. 다른 점이 있다면 크고, 작고가 아닌 갯수, 증가가 아닌 감소라는 부분인데 크기가 아닌 갯수기 때문에 max(직전횟수 + 1, 기존 dp[i] 횟수)이 되고, 증가가 아닌 감소는 값 입력을 거꾸로 받고 증가로 풀면 된다. #include using namespac..

http://www.acmicpc.net/problem/11055 풀이) 1 ~ N 순으로 인덱스가 증가될 때 이중포문으로 j = 1부터 해당 인덱스 전까지 비교하는 과정을 통해 dp를 채워나가는 방식이다. 당연히 현재 idx인 A[i]보다 A[j]가 작을 때만 해당되고, 해당 인덱스에서 가장 큰 값을 넣어야하기 때문에 max비교를 통해 모든 경우를 전부 비교해보고 가장 큰 값을 대입해준다. 글로 설명이 어려운 부분이 존재하는 것 같다. #include using namespace std; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int N, ANS = -1; int A[1001], DP[1001]; cin >> N; for..

http://www.acmicpc.net/problem/2004 2004번: 조합 0의 개수 첫째 줄에 정수 $n$, $m$ ($0 \le m \le n \le 2,000,000,000$, $n \ne 0$)이 들어온다. www.acmicpc.net 풀이) 1676(팩토리얼 0의 개수)의 문제에 조합개념이 추가된 문제이다. 결국 0의 개수는 (2, 5)가 몇쌍있는지 갯수를 구하면 답이 된다. 그렇기 때문에 nCm 조합개념을 적용하여 2와 5의 개수를 세고 둘 중 적은 것이 0의 개수가 된다. #include using namespace std; int ans(int n, int x) { int ans = 0; for (long long i = x; i > n >> m; two = ans(n, 2) - a..

http://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 풀이) 대표적인 그리디알고리즘 문제이다. 우선 회의들을 정렬을 해야하는데, 정렬의 조건은 다음과 같다. 1) 회의의 종료시간이 빠른순으로 2) 1번 조건이 같다면, 시작이 빠른 순으로 정렬을 하면 답을 구할 수 있다. 여기서 2번 조건이 조금 헷갈렸는데, 현실에선 그럴 일이 없겠지만 2번 조건이 없다면 8 8, 7 8이 들어왔을 때 역순으로 정렬을 한다면 8 8만 증가되겠지만, 2번 조건이 추가된다면 7 8 -> 8 8 이렇게 2번이 되기때문에 필요하다. #include #include #include using ..

http://www.acmicpc.net/problem/1929 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net 풀이) 소수의 정의를 이용해서 풀어보았다. 사실 n / 2가 아닌 루트n으로 하면 더 최적의 알고리즘이 되지만, sqrt를 구현하지않았고, 대신 100만의 제한에 맞춰서 100만루트인 1000을 최대값으로 설정해두었다. #include using namespace std; int is_prime(int n) { int i; if (n > N; for (int i = ..

http://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 풀이) 각 인덱스(i라 가정)마다 뒤로 나아가면서 누적합이 0보다 크면 계속 더해지는 그 순간마다 max(dp[i], sum)을 dp[i]에 갱신해주면 된다. #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n, ans = -1001; int a[100001], dp[100001..