개발하지연

문제 n×m의 0, 1로 된 배열이 있다. 이 배열에서 1로 된 가장 큰 정사각형의 크기를 구하는 프로그램을 작성하시오. 0 1 0 0 0 1 1 1 1 1 1 0 0 0 1 0 위와 같은 예제에서는 가운데의 2×2 배열이 가장 큰 정사각형이다. 기록 (dp 11일차) 시간을 좀 줄여보고 싶어서 여러가지 해봤는데 다 비슷했다..ㅎ 이차원 배열에 (i, j)를 오른쪽 아래 모서리로 갖는 1로 구성된 최대 정사각형의 길이를 저장한다. 위의 문제의 예시인 경우 다음과 같이 배열에 기록된다. 여기서 max값을 출력하면 1로 구성된 최대 정사각형이 나온다. 0 1 0 0 0 1 1 1 1 1 2 0 0 0 1 0 아래와 같은 경우, 이차원 배열의 구성과 최대 정사각형을 구하는 과정을 정리해보았다. 각 칸(i, j..

문제 상근이가 1학년 때, 덧셈, 뺄셈을 매우 좋아했다. 상근이는 숫자가 줄 지어있는 것을 보기만 하면, 마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 사이에는 '+' 또는 '-'를 넣어 등식을 만들며 놀고 있다. 예를 들어, "8 3 2 4 8 7 2 4 0 8 8"에서 등식 "8+3-2-4+8-7-2-4-0+8=8"을 만들 수 있다. 상근이는 올바른 등식을 만들려고 한다. 상근이는 아직 학교에서 음수를 배우지 않았고, 20을 넘는 수는 모른다. 따라서, 왼쪽부터 계산할 때, 중간에 나오는 수가 모두 0 이상 20 이하이어야 한다. 예를 들어, "8+3+2-4-8-7+2+4+0+8=8"은 올바른 등식이지만, 8+3+2-4-8-7이 음수이기 때문에, 상근이가 만들 수 없는 등식이다. 숫자가 주어졌을..

문제 우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 예를 들어, 30원을 만들기 위해서는 1원짜리 30개 또는 10원짜리 2개와 5원짜리 2개 등의 방법이 가능하다. 동전의 종류가 주어질 때에 주어진 금액을 만드는 모든 방법을 세는 프로그램을 작성하시오. 기록 (dp 9일차) 동전의 조합 순서가 엇갈리면 여러개로 세어질 수 있기 때문에 (ex. 1+1+2 = 2+1+1) 동전 순차적으로 반복문 돌면서 방법개수를 갱신해나가야한다. 코드 import sys input = sys.stdin.readline T = int(input()) for _ in range(T): N = i..

문제 네모 왕국의 왕인 진경대왕은 왕국의 영토를 편하게 통치하기 위해서 1X1의 단위 구역을 여러 개 묶어서 하나의 거대 행정구역인 주지수(州地數, 마을의 땅을 셈)를 만들 예정이다. 진경대왕은 주지수를 만들기 위해서 일정한 직사각형 범위 내에 살고 있는 사람 수를 참고 자료로 쓰고 싶어한다. 진경대왕은 굉장히 근엄한 왕이기 때문에 당신에게 4개의 숫자로 직사각형 범위를 알려줄 것이다. 예를 들어, 위와 같이 사람이 살고 있다고 가정할 때 의 직사각형 범위의 사람 수를 알고 싶다면 진경대왕은 네 개의 정수 1 1 3 2를 부를 것이다. 마찬가지로 는 1 1 1 4, 은 1 1 4 4가 될 것이다. 진경대왕을 위하여 이 참고 자료를 만들어내는 프로그램을 작성해보자. 기록 (dp 9일차) 어제 엄청 비슷한 ..