블로그 옮겼습니다
문제 링크 \(0\lt{N}\le{10^3}\)\(0\lt{K}\le{10^6}\)문제는 간단하다. N개의 사람이 있고 K개의 경기가 있다.모든 경기는 적어도 한명은 참가되어야하지만 딱 한사람만 참가할 수 있다.각 사람은 적어도 한 경기는 해야하고 한 사람은 여러개의 경기를 할 수가 있다.이 때 경기가 배정되는 경우의 수를 구하는 문제이다. 우선 K가 10^6인건 훼이크라는 것을 알 수가 있다. 왜냐하면 K가 N보다 크면 모든 사람에게 적어도한경기씩 배정할 수가 없기 때문이다. 그렇기 때문에 K > N 이면 바로 0 을 출력하고 넘어간다면K > T; while(T--){ memset(dp,0,sizeof(dp)); dp[0][0] = 1; cin >> N >> K; if(K > N){ cout
문제 링크 \( N\le{10^6}\)자연수 N이 주어진다. N을 네개의 소수의 합으로 분리할 수 있으면 그 네개의 수를 출력하고불가능하면 -1을 출력하는 문제이다. 우선 골드바흐의 추측이라는 것이 있다. 2보다 큰 짝수는 무조건 두개의 소수의 합으로 나타낼 수 있다는 것이다.내가 알기론 이미 꽤 큰 수(적어도 PS에서 주어지는 입력의 범위보단 큰 수) 까지는컴퓨터로 일일이 돌려보아 증명이 되었다고 알고있다. 그러니까 맞다고 생각하고 풀면된다 ㅎㅎ일단 입력으로 주어진 N이 홀수일 때와 짝수일 때로 나누어 보자.만약 홀수라면 골드바흐의 추측을 적용하기 위해 이를 짝수로 만들어 줘야 하므로 우선 하나의 수를 빼야하는데너무 많이 빼면 2이하가 될 수도 있으므로 가장 적게 빼는게 최선이므로 가장 작은 홀수 소수..
문제 링크 \(1\le{N}\le{10^5} \)N 개의 음이 아닌 정수가 주어지고 부분 배열 A[i~j]중에 sum(i~j) * min(i~j) 가 가장 큰 것의 값을구하는 문제이다. 이 문제를 O(NlgN) 과 O(N) 이렇게 두가지 방법으로 풀어보았다.우선 첫번째로 O(NlgN) 에 푸는 방법이다.방법은 이렇다. 일단 잘 생각해보면 구간의 min 값이 정해졌다면 min값이 그 것으로 유지되는 한가장 많은 수를 더하는 것이 최적이라는 것이다. 그렇기 때문에 어떤 하나의 숫자 A[k] 부터 시작해서왼쪽, 오른쪽으로 시작한 수 A[k] 보다 더 작은 수가 나오기 전까지 쭉쭉 확장시켜보자.그럼 min(i~j)값이 A[k] 일 때의 최대 점수이다. 그렇다면 min(i~j) 값은 N개 각각의 정수가 될 수가 ..