공부혜옹

배열의 원소값이 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이니 결국 우리가 ..

포도주 시식 시간 제한메모리 제한제출정답맞은 사람정답 비율 2 초 128 MB 68835 24484 17499 33.777% 문제 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규칙이 있다. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다. 연속으로 놓여 있는 3잔을 모두 마실 수는 없다. 효주는 될 수 있는 대로 많은 양의 포도주를 맛보기 위해서 어떤 포도주 잔을 선택해야 할지 고민하고 있다. 1부터 n까지의 번호가 붙어 있는 n개의 포도주 잔이 순서대로 테이블 위에 놓여 있고, 각 포도주 잔에 들어있..

이친수 성공분류 시간 제한메모리 제한제출정답맞은 사람정답 비율 2 초 128 MB 57925 23149 17226 38.159% 문제 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않는다. 이친수에서는 1이 두 번 연속으로 나타나지 않는다. 즉, 11을 부분 문자열로 갖지 않는다. 예를 들면 1, 10, 100, 101, 1000, 1001 등이 이친수가 된다. 하지만 0010101이나 101101은 각각 1, 2번 규칙에 위배되므로 이친수가 아니다. N(1 ≤ N ≤ 90)이 주어졌을 때, N자리 이친수의 개수를 구하는 프로그램을 작성하시오. 입..