(C++) - 백준(BOJ) 1915번 : 가장 큰 정사각형
https://www.acmicpc.net/problem/1915 1915번: 가장 큰 정사각형 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. www.acmicpc.net dp문제였습니다. 풀이방법 2 X 2짜리 정사각형을 생각합니다. i행 j열이 1이라면 이전에 가장 큰 정사각형의 한 변의 길이가 저장된 (i-1,j-1), (i-1,j), (i,j-1) 위치의 값들중 최소인값 + 1을 저장합니다. 점화식으로 나타낸다면 min({square[i-1][j-1],square[i-1][j],square[i][j-1]}) + 1 Code #include #define INF 0x3f3f3f3f using namespace std; int n,..
(C++) - 백준(BOJ) 16195번 : 1, 2, 3 더하기 9
https://www.acmicpc.net/problem/16195 16195번: 1, 2, 3 더하기 9 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. 단, 사용한 수의 개수는 m개 이하 이어야 한다. www.acmicpc.net dp로 해결한 문제였습니다. 풀이방법 1,2,3을 이용해 i이라는 숫자를 j개로 만들기 위한 점화식은 다음과 같습니다. d[i][j] = d[i-1][j-1] + d[i-2][j-1] + d[i-3][j-1] 1을 사용했을 때 숫자를 1개를 소모한 경우 + 2를 사용했을 때 숫자를 1개 소모한 경우 + 3을 사용했을 때 숫자를 1개 소모한 경우라고 풀어서 쓸 수 있습니다. Code(Bottom Up..
(C++) - 백준(BOJ) 15592번 : 1, 2, 3 더하기 7
https://www.acmicpc.net/problem/15992 15992번: 1, 2, 3 더하기 7 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. 단, 사용한 수의 개수는 m개 이어야 한다. www.acmicpc.net dp 문제였습니다. top-down으로 해결했습니다. 풀이방법 1,2,3을 이용해 i이라는 숫자를 j개로 만들기 위한 점화식은 다음과 같습니다. d[i][j] = d[i-1][j-1] + d[i-2][j-1] + d[i-3][j-1] 1을 사용했을 때 숫자를 1개를 소모한 경우 + 2를 사용했을 때 숫자를 1개 소모한 경우 + 3을 사용했을 때 숫자를 1개 소모한 경우라고 풀어서 쓸 수 있습니다. Cod..