공부혜옹

제일 먼저 문제 푸는방법을 효율적이지 않은 방법으로 막 생각해보았다 1. 숫자를 전부 준비한다 2. 재귀를 이용해 10의 n제곱으로 나누면서 각 자리수의 크기를 확인한다 블로그에 쓰기도 부끄러운 해결방법이었지만 일단 이러한 과정을 통해 당연히 시간초과가 날것이니 다른 방법을 찾아야지라는 생각을 하게 되었다. 사실 DP 문제이기 때문에 점화식을 찾으면 되는데 점화식 찾는것에 자신이 없다보니 브루트포스로 밀 수 있는지 한번 생각해봤다. 이제 어쩔 수 없이 점화식을 찾아보자 우선 DP배열의 메모이제이션을 어떻게 배당할 것인가를 결정했다 그다음 점화식을 찾기위해 예시로 dp[2][4]를 분석해보았다 dp[2][4]란 두자릿수의 숫자중 4로 끝나는 오름수의 갯수를 뜻한다. 두자릿수중 끝자리가 4이니 결국 우리가 ..

#include #include #include using namespace std; int n, m, t; // 문제의 수, 문제에 대한 정보의 개수 int parent[51]; int party[51][51]; int can; vector knowTrue; int find (int x) { if(x == parent[x]){ return x; } return x = find(parent[x]); } void unionset (int x, int y) { x = find(x); y = find(y); parent[x] = y; } int check(int i) { for (int j = 0; j < t; j++) { //진실된 사람 있으면 if (find(party[i][0]) == find(knowT..

#include #define endl "\n" using namespace std; int N, K, Answer; int Add_Water(int x) { int Cnt = 0; while (x > 0) { if (x % 2 == 1) { Cnt++; } x = x / 2; } return Cnt; } int main(void) { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> N >> K; if (N

문제집 시간 2 초 128 MB 12386 5791 4365 46.895% 문제 민오는 1번부터 N번까지 총 N개의 문제로 되어 있는 문제집을 풀려고 한다. 문제는 난이도 순서로 출제되어 있다. 즉 1번 문제가 가장 쉬운 문제이고 N번 문제가 가장 어려운 문제가 된다. 어떤 문제부터 풀까 고민하면서 문제를 훑어보던 민오는, 몇몇 문제들 사이에는 '먼저 푸는 것이 좋은 문제'가 있다는 것을 알게 되었다. 예를 들어 1번 문제를 풀고 나면 4번 문제가 쉽게 풀린다거나 하는 식이다. 민오는 다음의 세 가지 조건에 따라 문제를 풀 순서를 정하기로 하였다. N개의 문제는 모두 풀어야 한다. 먼저 푸는 것이 좋은 문제가 있는 문제는, 먼저 푸는 것이 좋은 문제를 반드시 먼저 풀어야 한다. 가능하면 쉬운 문제부터 풀..

줄 세우기 시간 제한메모리 제한제출정답맞은 사람정답 비율 2 초 128 MB 21910 12030 7818 53.137% 문제 N명의 학생들을 키 순서대로 줄을 세우려고 한다. 각 학생의 키를 직접 재서 정렬하면 간단하겠지만, 마땅한 방법이 없어서 두 학생의 키를 비교하는 방법을 사용하기로 하였다. 그나마도 모든 학생들을 다 비교해 본 것이 아니고, 일부 학생들의 키만을 비교해 보았다. 일부 학생들의 키를 비교한 결과가 주어졌을 때, 줄을 세우는 프로그램을 작성하시오. 입력 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는..

Cubeditor 0.5 초 128 MB 5904 1850 1371 33.793% 문제 Cubelover는 프로그래밍 언어 Whitespace의 코딩을 도와주는 언어인 Cubelang을 만들었다. Cubelang을 이용해 코딩을 하다보니, 점점 이 언어에 맞는 새로운 에디터가 필요하게 되었다. 오랜 시간 고생한 끝에 새로운 에디터를 만들게 되었고, 그 에디터의 이름은 Cubeditor이다. 텍스트 에디터는 찾기 기능을 지원한다. 대부분의 에디터는 찾으려고 하는 문자열이 단 한 번만 나와도 찾는다. Cubelover는 이 기능은 Cubelang에 부적합하다고 생각했다. Cubelang에서 필요한 기능은 어떤 문자열 내에서 부분 문자열이 두 번 이상 나오는 문자열을 찾는 기능이다. 이때, 두 부분 문자열은 ..

부분 문자열 1 초 512 MB 3992 1271 932 38.672% 문제 문자열 S의 부분 문자열이란, 문자열의 연속된 일부를 의미한다. 예를 들어, "aek", "joo", "ekj"는 "baekjoon"의 부분 문자열이고, "bak", "p", "oone"는 부분 문자열이 아니다. 문자열 S와 P가 주어졌을 때, P가 S의 부분 문자열인지 아닌지 알아보자. 입력 첫째 줄에 문자열 S, 둘째 줄에 문자열 P가 주어진다. 두 문자열은 빈 문자열이 아니며, 길이는 100만을 넘지 않는다. 또, 알파벳 소문자로만 이루어져 있다. 출력 P가 S의 부분 문자열이면 1, 아니면 0을 출력한다. kmp알고리즘을 이용하여 풀이하였다. 처음엔 find함수를 썼는데 시간초과가 났다. find 함수는 O(N*M)인데 ..

찾기 2 초 256 MB 23546 6785 3759 28.822% 문제 워드프로세서 등을 사용하는 도중에 찾기 기능을 이용해 본 일이 있을 것이다. 이 기능을 여러분이 실제로 구현해 보도록 하자. 두 개의 문자열 P와 T에 대해, 문자열 P가 문자열 T 중간에 몇 번, 어느 위치에서 나타나는지 알아내는 문제를 '문자열 매칭'이라고 한다. 워드프로세서의 찾기 기능은 이 문자열 매칭 문제를 풀어주는 기능이라고 할 수 있다. 이때의 P는 패턴이라고 부르고 T는 텍스트라고 부른다. 편의상 T의 길이를 n, P의 길이를 m이라고 하자. 일반적으로, n ≥ m이라고 가정해도 무리가 없다. n 0 && H[i] != N[matched]) matched = pi[matched - 1]; if (H[i] == N[ma..