1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
#include <algorithm>
using namespace std;
int candy[1002][1002];
int d[1002][1002];
int r,c;
 
int main()
{
    cin >> r >> c;
    for (int i = 1;i <= r; ++i)
    for (int j = 1; j <= c; ++j)
    {
        cin >> candy[i][j];
    }
    
    for (int i = 1; i <= r; ++i)
    for (int j = 1; j <= c; ++j)
    {
        d[i][j] = max(max(d[i - 1][j], d[i - 1][j - 1]), d[i][j - 1]) + candy[i][j];
    }
    cout << d[r][c] << endl;
    return 0;
}
cs
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 <iostream>
#include <algorithm>
using namespace std;
int candy[1002][1002];
int d[1002][1002];
int r,c;
 
int main()
{
    cin >> r >> c;
    for (int i = 1;i <= r; ++i)
    for (int j = 1; j <= c; ++j)
    {
        cin >> candy[i][j];
    }
    d[1][1] = candy[1][1];
    for (int i = 1; i <= r; ++i)
    for (int j = 1; j <= c; ++j)
    {
        if (i + 1 <= r && d[i + 1][j] < d[i][j] + candy[i + 1][j])
            d[i + 1][j] = d[i][j] + candy[i + 1][j];
        if (j + 1 <= c && d[i][j+1] < d[i][j] + candy[i][j+1])
            d[i][j + 1] = d[i][j] + candy[i][j + 1];
        if (j + 1 <= c && i + 1 <= r && d[i + 1][j + 1] < d[i][j] + candy[i + 1][j + 1])
            d[i + 1][j + 1] = d[i][j] + candy[i + 1][j + 1];
    }
    cout << d[r][c] << endl;
    return 0;
}
cs


저작자표시 비영리 (새창열림)

'백준 온라인 저지' 카테고리의 다른 글

백준 10942: 팰린드롬?  (0) 2018.07.31
백준 1890: 점프  (0) 2018.07.31
백준 2263: 트리의 순회  (0) 2018.07.31
백준 1931: 회의실 배정  (0) 2018.07.30
백준 11047: 동전 0  (0) 2018.07.30

인덱스 때문에 고생한 문제 일단 문제를 봤을 때 벙찌게 된다.. 내가 작성하는 풀이들은 알고리즘 초보이거나, 나중에 내가 푼 문제를 되돌아 보기 위한 것이므로 이 문제를 볼 때 상당한 난해함을 느끼게 되지만 한 번 생각해보자.


먼저 포스터 오더와 인 오더에 대해 생각해보자. 결론부터 말하자면 포스트 오더가 마지막에 방문하는 노드는 루트이다. 왜 그럴까? 포스트오더는 시작하는 L R 노드 순으로 방문하기 때문이다. 그러면 포스트 오더로부터 루트를 알 수 있다. 그러면 루트를 알 수 있다면 인 오더에서 L트리와 R트리를 구분 할 수 있다. 인오더는 L 노드 R 순이기 때문이다. 자연스럽게 포스트오더에 맨 마지막에 있는 수를 기준으로 인오더의 왼쪽은 L 트리 오른쪽은 R트리이다. 그러면 이제 프리오더 순으로 방문하기 위해 재귀적인 방법을 사용하면 된다. divide and conquer다.  다시 L트리와 R트리에서 포스트오더 인오더의 범위를 지정해주고 계속해서 재귀해나가면 된다. 방법을 알고 있음에도 나는 한참 해맸는데 멍청하게  go 함수 return문 바로 뒤인 22,23라인에서 절대적 배열의 주소를 사용하려고 했었기 때문이다. 절대적 주소를 사용할 경우도 있겠지만.. 왠만하면 상대적인 주소를 사용하는게 오류를 범할 가능성이 적은 것 같다. 재귀함수를 코딩하면 그 내부에서 어떤 일이 일어나는지 알아야하겠지만 보이지 않으니 놓치는 부분이 있을 수도 있기 때문에 상대적인 주소를 사용하자!



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
30
31
32
33
34
35
36
37
38
39
40
#include <iostream>
using namespace std;
int n;
int post[100001];
int in[100001];
void go(int po_start, int po_end, int in_start, int in_end)
{
    if (po_start > po_end || in_start > in_end)
        return;
    int root = post[po_end];
    cout << root << " ";
    int index = 0;
    //인오더 배열에서 root의 위치를 찾아준다.
    for (int i = in_start; i <= in_end; ++i)
    {
        if (in[i] == root)
        {
            index = i;
            break;
        }    
    }
    go(po_start, po_start + (index - in_start) - 1, in_start, index - 1);
    go(po_start + (index - in_start), po_end - 1, index + 1, in_end);
    return;
}
int main()
{
    cin >> n;
    for (int i = 0; i < n; ++i)
    {
        cin >> in[i];
    }
    for (int i = 0; i < n; ++i)
    {
        cin >> post[i];
    }
    go(0, n - 1, 0, n - 1);
    cout << endl;
    return 0;
}
cs


저작자표시 비영리 (새창열림)

'백준 온라인 저지' 카테고리의 다른 글

백준 1890: 점프  (0) 2018.07.31
백준 11048: 이동하기  (0) 2018.07.31
백준 1931: 회의실 배정  (0) 2018.07.30
백준 11047: 동전 0  (0) 2018.07.30
백준 14501: 퇴사  (0) 2018.07.30

그리디 알고리즘을 사용한 문제 증명은 없지만 직관적으로 보면 회의가 가장 빨리 끝나는 순으로 배정을 한다. 백준 입력이 정렬되어있는지 알수 없으므로 정렬도 해준다. 시간복잡도는 O(n) 보다 정렬해야하니깐 O(nlogn) 일수도


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
30
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
 
vector<pair<int,int>> v; 
int main()
{
    int n;
    int end_time = 0;
    int ans = 0;
    
    cin >> n;
    int temp1, temp2;
    for (int i = 0; i < n; ++i)
    {
        cin >> temp1 >> temp2;
        v.push_back(make_pair(temp2, temp1));
    }
    sort(v.begin(), v.end());
    for (int i = 0; i < n; ++i)
    {
        if (v[i].second >= end_time){
            end_time = v[i].first;
            ++ans;
        }
    }
    cout << ans << endl;
    return 0;
}
cs


저작자표시 비영리 (새창열림)

'백준 온라인 저지' 카테고리의 다른 글

백준 11048: 이동하기  (0) 2018.07.31
백준 2263: 트리의 순회  (0) 2018.07.31
백준 11047: 동전 0  (0) 2018.07.30
백준 14501: 퇴사  (0) 2018.07.30
백준 1182: 부분집합의 합  (0) 2018.07.29

+ Recent posts

티스토리툴바