4095 최대 정사각형

1915 가장 큰 정사각형 과 거의 같은 문제이다.
다른 점은 넓이 대신 한변의 길이만 출력하면 된다.

소스

1915 가장 큰 정사각형

n * m의 배열에 0,1 의 값이 있는데, 1의 값으로 채워져 있는 가장 큰 정사각형의 넓이를 구하는 문제이다.

이 문제는 DP로 해결이 가능한데, dp를 구성하는 방법은 다음과 같이 하면 된다.


(i = 0~m-1, j = 0~n-1)
dp[0][j] = 좌표값이 1이면 1, 아니면 0.
dp[i][0] = 좌표값이 1이면 1, 아니면 0.

i,j 좌표값이 1일 때,
dp[i][j] =  1+MIN(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])

이 때 나온 dp 값중에 최대값을 저장해서, 넓이를 출력하면 된다.

소스

4998 저금

N원에서 년 b%복리로 M원을 넘기려할 때 몇년이 걸리는가를 구하는 문제이다.

복리기 때문에 년마다 N원에 계속 현재 N원의 b%씩 쌓아가면 된다.

소스

2636 치즈

2638 치즈 와 같은 문제인데, 여기서 두 면에 닿아야 녹는것을 한 면으로 고치고, 전부 녹기 바로 전날의 치즈 개수만 구해주면 된다.

소스

2355 시그마

두 수 i,j 사이에 있는 정수의 합을 구하는 문제이다.

두 수중 큰것을 i로 놓고, 작은것을 j로 놓아준 다음,
1부터 i 까지의 합에서 1부터 j까지의 합을 빼주면 된다.

소스

1236 성 지키기

주어진 크기의 모든 행, 모든 열에 경비원을 한명씩은 배치하려고 할 때 추가로 배치해야하는 경비원의 수의 최솟값을 찾는 문제이다.

각 행과 각 열에 경비원이 몇명이나 배치되어있는지 확인하고,
행에 비어있는 경비원의 수와 열에 비어있는 경비원의 수중 큰값을 고르면 필요한 경비원의 수의 최소가 된다.

한 경비원이 한 행,한 열을 차지하도록 놓을 수 있기 때문이다.

소스

2638 치즈

치즈가 외부 공기 두 면이상에 노출되면 녹는다고 한다.
이 때 치즈가 모두 녹으려면 몇일이 걸리는가를 구하는 문제이다.
단, 내부에 뚫려있는곳은 녹는것과 관련이 없다.

맵을 한바퀴 돌면서 치즈가 있다면 치즈의 4 방향을 살펴봐서 2 방향이상이 외부와 접촉한다면 녹이면 된다.

여기서 외부와 내부를 구별하는 방법은, 외부는 항상 0,0과 이어져있다. 따라서 0,0을 시작으로 연결되어있는 모든 위치에 외부라는 표시를 해두고, 치즈를 녹일때도 그 외부인 표시만으로 판별해주면 된다.

소스