www.acmicpc.net/problem/1915 

 

1915번: 가장 큰 정사각형

첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다.

www.acmicpc.net

 

정사각형을 만족하기 위해서 어떤 규칙이 필요할까?

행렬 i, j 를 기준으로 왼쪽, 위, 왼쪽 위가 모두 1인 것만이 정사각형이 된다.

이걸 확장시켜주면, 최종적인 점화식은 D[i][j]=min(d[i−1][j],d[i][j−1],d[i−1][j−1])+1 이 된다.

물론 조건문으로 현재 위치가 1이고 그 주변도 1임을 미리 따져줘야 한다.

 

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <cstdio>
#include <algorithm>
using namespace std;
 
int a[1001][1001], n, m;
 
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            scanf("%1d", &a[i][j]);
 
    int res = 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            if (a[i][j] && a[i - 1][j] && a[i][j - 1] && a[i - 1][j - 1]) {
                a[i][j] += min({ a[i][j - 1], a[i - 1][j - 1], a[i - 1][j] });
            }
            res = max(res, a[i][j]);
        }
    }
    printf("%d\n", res * res);
    
    return 0;
}
 cs

 

a 배열에는 정사각형을 만족하는 크기가 들어가 있을테니 제곱의 형태로 출력해주면 된다.

'BOJ' 카테고리의 다른 글

BOJ 3190 뱀  (0) 2020.12.19
BOJ 1446 지름길  (0) 2020.12.16
BOJ 7579 앱  (0) 2020.12.13
BOJ 5052 전화번호 목록  (0) 2020.12.10
BOJ 5014 스타트링크  (0) 2020.12.10
KcodeKrockseed 님의 블로그입니다.

www.acmicpc.net/problem/7579

 

7579번: 앱

입력은 3줄로 이루어져 있다. 첫 줄에는 정수 N과 M이 공백문자로 구분되어 주어지며, 둘째 줄과 셋째 줄에는 각각 N개의 정수가 공백문자로 구분되어 주어진다. 둘째 줄의 N개의 정수는 현재 활

www.acmicpc.net

 

배낭 문제의 변형이다. 메모리와 비용이 주어지는데 dp테이블을 메모리를 기준으로 채워야 하나?

생각했는데 비용을 기준으로 dp테이블을 채워줘야 한다.

 

예제를 보면 

 

30 10 20 35 40

3 0 3 5 4

 

가 주어지는데 

0   1   2  3   4  5   6   7  8  9   10   11   12  13   14  15

10 10 10 40 50 50 60 80 80 85 100 100 115 115 115 135

이런 식으로 테이블을 채워주고 그때의 m값의 인덱스를 찾아주면 된다.

 

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <iostream>
#include <algorithm>
using namespace std;
 
int n, k, sum, w[101], v[101], d[100001];
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
 
    cin >> n >> k;
    for (int i = 0; i < n; ++i) cin >> w[i];
    for (int i = 0; i < n; ++i) cin >> v[i], sum += v[i];
 
    for (int i = 0; i < n; ++i)
        for (int j = sum; j >= v[i]; --j)
            d[j] = max(d[j], d[j - v[i]] + w[i]);
    
    //for (int i = 0; i <= sum; ++i) cout << d[i] << ' ';
    //cout << endl;
 
    int i;
    for (i = 0; i < sum && d[i] < k; ++i);
    cout << i << endl;
 
    return 0;
}
 cs

 

'BOJ' 카테고리의 다른 글

BOJ 1446 지름길  (0) 2020.12.16
BOJ 1915 가장 큰 정사각형  (0) 2020.12.13
BOJ 5052 전화번호 목록  (0) 2020.12.10
BOJ 5014 스타트링크  (0) 2020.12.10
BOJ 11066 파일 합치기  (0) 2020.12.05
KcodeKrockseed 님의 블로그입니다.

 

앞쪽에 있는 기능이 전부 개발되었다면 앞에서부터 기능이 개발되지 않은 것이 나올 때까지 pop 해주고

그 cnt를 answer에 저장해주면 된다.

 

우선 progresses와 speeds를 전부 큐에 넣어주고 반복문을 통해 0번 위치의 기능을 수행하는 데에

얼마나 걸리는지 세준다. 이후 현재 날 * speed의 front + q의 front가 100보다 크다면 그 기능도

이미 완료되었기 때문에 pop 해주면 된다.

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <string>
#include <vector>
#include <queue>
using namespace std;
 
vector<int> solution(vector<int> progresses, vector<int> speeds) {
    vector<int> answer;
    queue<int> q, sp;
 
    for (int i : progresses) q.push(i);
    for (int i : speeds) sp.push(i);
    
    while (!q.empty()) {
        int cnt = 1;
        int day = 0;
        int cur = q.front(); q.pop();
        int spd = sp.front(); sp.pop();
        
        while(cur < 100) cur += spd, ++day;
 
        while(!q.empty() && sp.front() * day + q.front() >= 100) {
            sp.pop(), q.pop(), ++cnt;
        }
        
        answer.push_back(cnt);
    }
    
    return answer;
}
 cs

'Programmers' 카테고리의 다른 글

프로그래머스 실패율  (0) 2020.12.26
C++ 단어 변환  (0) 2020.11.28
[프로그래머스 C++] 카카오프렌즈 컬러링북  (0) 2020.09.28
[프로그래머스 C++] 소수 찾기  (0) 2020.09.27
[프로그래머스 C++] 완주하지 못한 선수  (0) 2020.09.26
KcodeKrockseed 님의 블로그입니다.

+ Recent posts

티스토리툴바