공부혜옹

배열의 원소값이 1인 부분만 사각형의 일부가 될 수 있기 때문에 0인 부분을 제외하고 생각한다. 1을 만났을때 이것이 정사각형일지 아닐지를 판단하는것이 문제 1을 만날 경우 1의 왼쪽, 왼쪽 대각선위, 위쪽 총 세부분을 검사해 가장 작은 수를 찾아 +1해주면 그것이 해당 사각형 한변의 최대 길이가 된다. 이것을 식으로 표현하면 다음과 같다 arr[i][j] = min(arr[i-1][j], arr[i-1][j-1], arr[i][j-1]) +1 예상치 못하게 fail을 받은 문제인데 '다음 n개의 줄에는 m개의 숫자로 배열이 주어진다.' 이 주어지는 숫자 배열이 실제 숫자가 아니고 string으로 주어지기 때문에 int가 아닌 string으로 받아 인덱스 - 48을 해주어야한다. #include #inc..

도형에다가 dp 문제이기 때문에 도형을 일단 하나하나 그려보면서 규칙성을 찾고자 했다. 3X4사이즈의 벽을 그리던 와중 3X2벽에서 나온 타일의 패턴을 이용할 수 있겠다는 생각이 들어서 바로 3 * 3 = 9 가지구나! 라고 생각하고 코드를 구현했는데 당연히 틀렸다. 왜냐하면 3X2의 패턴말고 추가 패턴이 2가지 더 나오기 때문이다 (빨간 동그라미 친 패턴) 풀겠다는 의지를 가지고 3X8까지 그려본 결과 각 단계별로 추가 패턴은 2개가 나온다는 것을 확인했다. 3X6의 패턴을 파악하던중 중복이 나올 수 있다는것을 알게되었고 중복을 피하고자 하는 방법을 찾기 시작했다. 패턴을 케이스 별로 나누어 생각하는것인데 첫번째 케이스의 경우 이전과 같은 논리로 3X2의 패턴경우의 수 * 3X4의 패턴경우의 수 를 해..

제일 먼저 문제 푸는방법을 효율적이지 않은 방법으로 막 생각해보았다 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에서 필요한 기능은 어떤 문자열 내에서 부분 문자열이 두 번 이상 나오는 문자열을 찾는 기능이다. 이때, 두 부분 문자열은 ..