How We Coding

<8-8> 수학 - 둥근 모양의 국가들 (CirclesCountry)

PS/Topcoder training2018. 7. 16. 11:15

### 수학 ###


### SRM 443 Div2 Level 2 ###



<소스트리>


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 <vector>
using namespace std;
 
double dist(int x1, int y1, int x2, int y2)
{
    return (x2-x1)*(x2-x1) + (y2-y1)*(y2-y1);
}
 
class CirclesCountry {
public:
    int leastBorders(vector <int> X, vector <int> Y, vector <int> R, int x1, int y1, int x2, int y2) {
        
        int ans=0;
        for(int i=0; i<X.size(); i++) {
            double d1 = dist(X[i], Y[i], x1, y1);
            double d2 = dist(X[i], Y[i], x2, y2);
            double r = (double)R[i]*R[i];
            if(d1 < r) ans++;
            if(d2 < r) ans++;
            if(d1 < r && d2 < r) ans -= 2;
        }
        return ans;
    }
};
cs


>>> 기본 아이디어는 시작 좌표와 목표 좌표가 둥근성에 포함되어 있으면 카운트.

>>> 예외처리 : 같은 성에 동시에 포함되어 있으면 카운트하면 안된다.

'PS > Topcoder training' 카테고리의 다른 글

<5-9> 전체탐색 - 마법의 숫자 (NumberMagicEasy)  (0) 2018.07.16
<5-8> 전체탐색 - 미로 만드는 사람 (MazeMaker)  (0) 2018.07.16
<8-4> 그리디 - 배치 시스템 (BatchSystem)  (0) 2018.07.16
<8-1> 탐색범위 한정 - 다양한 색상의 상자와 공 (ColorfulBoxesAndBalls)  (0) 2018.07.14
<7-5> DP - 악수 (HandShaking)  (0) 2018.07.04

<8-4> 그리디 - 배치 시스템 (BatchSystem)

PS/Topcoder training2018. 7. 16. 01:54

### Greedy ###


### SRM 481 Div2 Level 3 ###


<소스코드>


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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <algorithm>
#include <string>
#include <vector>
#include <map>
using namespace std;
 
typedef long long int lli;
 
struct P { 
    int i, duration; 
    P(int i, int duration) : i(i), duration(duration) {}
};
 
struct userInfo {
    vector<P> v;
    lli sum;
    userInfo(vector<P> v, lli sum) : v(v), sum(sum) {}
};
 
bool cmp(P a, P b)
{
    return a.i < b.i;
}
 
bool cmp2(userInfo a, userInfo b)
{
    return a.sum != b.sum ? a.sum < b.sum : a.v[0].i < b.v[0].i;
}
    
class BatchSystem {
public:
    vector<int> schedule(vector <int> duration, vector <string> user) {
        int userIdx=0;
        map<string, int> msi;
        vector<userInfo> info;
        for(int i=0; i<duration.size(); i++) {
            if(msi.find(user[i]) == msi.end()) {
                msi[user[i]] = ++userIdx;
                vector<P> v; v.push_back(P(i, duration[i]));
                info.push_back(userInfo(v, duration[i]));
            }
            else {
                int idx = msi[user[i]]-1;
                info[idx].sum += duration[i];
                info[idx].v.push_back(P(i, duration[i]));
            }
        }
            
        for(int i=0; i<info.size(); i++) {
            sort(info[i].v.begin(), info[i].v.end(), cmp);
        }
 
        sort(info.begin(), info.end(), cmp2);
        
        vector<int> ans;
        for(int i=0; i<info.size(); i++) {
            for(int j=0; j<info[i].v.size(); j++) {
                ans.push_back(info[i].v[j].i);
            }
        }
        return ans;
    }
};
 
cs


'PS > Topcoder training' 카테고리의 다른 글

<5-8> 전체탐색 - 미로 만드는 사람 (MazeMaker)  (0) 2018.07.16
<8-8> 수학 - 둥근 모양의 국가들 (CirclesCountry)  (0) 2018.07.16
<8-1> 탐색범위 한정 - 다양한 색상의 상자와 공 (ColorfulBoxesAndBalls)  (0) 2018.07.14
<7-5> DP - 악수 (HandShaking)  (0) 2018.07.04
<5-7> 전체탐색 - 고장난 로봇 (CrazyBot)  (0) 2018.07.03

<8-1> 탐색범위 한정 - 다양한 색상의 상자와 공 (ColorfulBoxesAndBalls)

PS/Topcoder training2018. 7. 14. 23:47

### SRM 464 Div2 Level 1 ###



<소스코드>


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <algorithm>
using namespace std;
 
class ColorfulBoxesAndBalls {
public:
    int getMaximum(int numRed, int numBlue, int onlyRed, int onlyBlue, int bothColors) {
        int ans=0;
        int minCnt = min(numRed, numBlue);
 
        ans = max(onlyRed+onlyBlue, bothColors*2) * minCnt;
        ans += ((numRed-minCnt) * onlyRed);
        ans += ((numBlue-minCnt) * onlyBlue);
        return ans;
    }
};
 
cs


>> 둘중 적은 것의 갯수만큼 섞을 수 있다. 그래서 그 최소개를 제대로 넣은 경우와 섞은 경우중 최대값이 정답이 된다.

>> 나머지에서는 자기 박스에 자기 공을 넣을 것이기 때문에 그 값을 더해주면 된다.

'PS > Topcoder training' 카테고리의 다른 글

<8-8> 수학 - 둥근 모양의 국가들 (CirclesCountry)  (0) 2018.07.16
<8-4> 그리디 - 배치 시스템 (BatchSystem)  (0) 2018.07.16
<7-5> DP - 악수 (HandShaking)  (0) 2018.07.04
<5-7> 전체탐색 - 고장난 로봇 (CrazyBot)  (0) 2018.07.03
<5-4> 전체탐색 - 회문 (ThePalindrome)  (0) 2018.07.01

<180709> 우선순위 큐 (Priority Queue)

Tutoring/SRF - B2018. 7. 10. 00:10

<180709>


### 우선순위 큐 ###


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
41
42
43
44
#define MAXN    100000
 
template<typename T>
struct Priority_queue {
    T heap[MAXN];
    int size;
    
    Priority_queue() : size(0) {}
    
    void push(T data) {
        int cur = ++size;
        int p = cur>>1;
 
        /*** Min Heap ***/
        while(p != 0 && heap[p] > data) {
            heap[cur] = heap[p];
            cur = p;
            p >>= 1;
        }
        heap[cur] = data;
    }
 
    bool empty() { return size == 0; }
    
    T top() { return heap[1]; }
 
    void pop() {
        if(size == 0) return ;
 
        int cur = 1, child = cur<<1;
 
        while(child < size) {
            if(child+1 < size && heap[child] > heap[child+1]) child|=1;
            if(heap[size] > heap[child]) {
               heap[cur] = heap[child];
               cur = child;
               child <<= 1;
            }
            else break;
        }
        heap[cur] = heap[size--];
    }
};
 
cs


>> Min Heap 으로 구현.

>> 루트의 인덱스는 1로 두고 구현.

>> push() : n번째 노드는 완전이진트리 기준 n번째 위치를 cur로, cur의 부모 인덱스를 p로 두고 시작.    

   부모노드와 비교하여, 현재 노드값이 부모노드의 값보다 작으면, 부모노드의 값을 현재노드 위치로 당긴다. (35라인)

   보통 스왑을 하지만, 나중에 자기 위치만 찾은다음 대입만 해주는 식으로 구현을 하였다.

   부모의 인덱스가 0이라는 것은 더이상 부모가 없다는 뜻. 즉, 15라인은 부모가 존재하는데, 부모의 값보다 대상 데이터의 값이 작다면 이과정을 반복.

>> pop() : 팝은 맨 마지막 데이터를 루트에 두고 자기자리를 찾아가는 과정으로 생각하면 된다.

  자기 자리를 찾아갈때는, 자식의 인덱스가 전체 사이트의 크기보다 작은지를 확인하면 된다. 

  자식의 인덱스가 사이즈보다 크다는 것은 더이상의 자식이 존재하지 않는다는 뜻.

  그리고 자식이 존재하는데(child < size), 두개의 자식이 존재한다면(child+1 < size) 둘중 작은 값을 가진 자식과 교환을 해야한다.!!


>> 구현 아이디어는 윤성우의 열혈 자료구조 + 생능 출판사의 천인국 저자 책. 학교 교잰데 이름 기억안남;;


<문제풀이>


[1927]  최소 힙 : http://boj.kr/1927


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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
/*** Min Heap ***/
/*** boj.kr/1927 ***/
 
#include <iostream>
using namespace std;
 
#define MAXN    100000
 
template<typename T>
struct Priority_queue {
    T heap[MAXN];
    int size;
    
    Priority_queue() : size(0) {}
    
    void push(T data) {
        int cur = ++size;
        int p = cur>>1;
 
        /*** Min Heap ***/
        while(p != 0 && heap[p] > data) {
            heap[cur] = heap[p];
            cur = p;
            p >>= 1;
        }
        heap[cur] = data;
    }
 
    bool empty() { return size == 0; }
    
    T top() { return heap[1]; }
 
    void pop() {
        if(size == 0) return ;
 
        int cur = 1, child = cur<<1;
 
        while(child < size) {
            if(child+1 < size && heap[child] > heap[child+1]) child|=1;
            if(heap[size] > heap[child]) {
               heap[cur] = heap[child];
               cur = child;
               child <<= 1;
            }
            else break;
        }
        heap[cur] = heap[size--];
    }
};
 
int main()
{
    cin.tie(NULL);
    std::ios::sync_with_stdio(false);
 
    int n;
    cin >> n;
 
    Priority_queue<int> pq;
    while(n--) {
        int k;
        cin >> k;
 
        if(k) pq.push(k);
        else {
            int ans;
            if(pq.empty()) ans = 0;
            else {
                ans = pq.top();
                pq.pop();
            }
            cout << ans << '\n';
        }
    }
}
 
cs




[11286] 절대값 힙 : http://boj.kr/11286


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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include <cstdio>
#include <vector>
#define MAXN    100000
 
using namespace std;
 
typedef pair<int, int> pii;
 
template<typename T>
struct Priority_queue {
    T heap[MAXN];
    int size;
    
    Priority_queue() : size(0) {}
    
    void push(T data) {
        int cur = ++size;
        int p = cur>>1;
 
        /*** Min Heap ***/
        while(p != 0 && (heap[p].first > data.first || ((heap[p].first == data.first) && (heap[p].second > data.second)))) {
            heap[cur] = heap[p];
            cur = p;
            p >>= 1;
        }
        heap[cur] = data;
    }
 
    bool empty() { return size == 0; }
    
    T top() { return heap[1]; }
 
    void pop() {
        if(size == 0) return ;
 
        int cur = 1, child = cur<<1;
 
        while(child < size) {
            if(child+1 < size) {
                if(heap[child].first > heap[child+1].first) child++;
                else if(heap[child].first == heap[child+1].first) {
                    if(heap[child].second > heap[child+1].second) child++;
                }
            }
            if(heap[size].first > heap[child].first || ((heap[size].first==heap[child].first)&&(heap[size].second > heap[child].second))) {
               heap[cur] = heap[child];
               cur = child;
               child <<= 1;
            }
            else break;
        }
        heap[cur] = heap[size--];
    }
 
};
 
int main()
{
    int n;
    scanf("%d", &n);
 
    Priority_queue<pii> pq;
    while(n--) {
        int k;
        scanf("%d", &k);
 
        if(k) {
            int tmp = k < 0 ? -k : k;
            pq.push(pii(tmp, k));
        }
        else {
            int ans;
            if(pq.empty()) ans=0; 
            else { ans = pq.top().second; pq.pop(); }
            printf("%d\n", ans);
        }
    }
}
 
cs


>> 절대값이 같으면 원래값이 작은 순으로 MinHeap 구현


>> 힙 구현한것을 바꾸지 않고 하는 방법 (referenced by kyujeong)


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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <iostream>
using namespace std;
 
#define MAXN    100000
 
template<typename T>
struct Priority_queue {
    T heap[MAXN];
    int size;
    
    Priority_queue() : size(0) {}
    
    void push(T data) {
        int cur = ++size;
        int p = cur>>1;
 
        /*** Min Heap ***/
        while(p != 0 && heap[p] > data) {
            heap[cur] = heap[p];
            cur = p;
            p >>= 1;
        }
        heap[cur] = data;
    }
 
    bool empty() { return size == 0; }
    
    T top() { return heap[1]; }
 
    void pop() {
        if(size == 0) return ;
 
        int cur = 1, child = cur<<1;
 
        while(child < size) {
            if(child+1 < size && heap[child] > heap[child+1]) child|=1;
            if(heap[size] > heap[child]) {
               heap[cur] = heap[child];
               cur = child;
               child <<= 1;
            }
            else break;
        }
        heap[cur] = heap[size--];
    }
};
 
int main()
{
    cin.tie(NULL);
    std::ios::sync_with_stdio(false);
 
    int n;
    cin >> n;
 
    Priority_queue<double> pq;
    while(n--) {
        double k;
        cin >> k;
 
        if(k > 0) pq.push(k+0.1);
        else if(k < 0) pq.push(-k);
        else {
            int ans;
            double top;
            if(pq.empty()) ans = 0;
            else {
                top = pq.top();
                if(top == (int)top) ans = -(int)top;
                else ans = (int)top;
                pq.pop();
            }
            cout << ans << '\n';
        }
    }
}
 
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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <cstdio>
using namespace std;
const int MAXN = 1e5 + 6;
 
template<typename T>
void swap(T *a, T *b) {
   T tmp = *a;
   *a = *b;
   *b = tmp;
}
 
template<typename T>
struct priority_queue {
   T arr[MAXN];
   int idx;
 
   priority_queue() :idx (0) {}
 
   bool empty() { return idx == 0; }
 
   int size() { return idx; }
 
   T top() { return arr[0]; }
 
   void push(T const &data) {
      arr[idx++] = data;      
      int curr = idx - 1;
      while (1) {
         if (curr == 0) break;
         int par = (curr - 1) / 2;
         if (arr[par] > arr[curr]) swap(&arr[par], &arr[curr]);
         curr = par;
      }
   }
 
   void pop() {
      arr[0] = arr[--idx];
      int curr = 0, next;
      while (curr * 2 + 1 < idx) {
         next = curr;
         if (arr[next] > arr[curr * 2 + 1]) next = curr * 2 + 1;
         if (curr * 2 + 2 < idx && arr[next] > arr[curr * 2 + 2]) next = curr * 2 + 2;
         if (next == curr) break;
         swap(&arr[curr], &arr[next]);
         curr = next;
      }
   }
};
 
int main() {
 
   priority_queue<int> pq;
   int n;
   scanf("%d", &n);
 
   for (int i = 0,d ; i < n; i++) {
      scanf("%d", &d);
      if (d == 0) {
         if (pq.empty()) printf("0\n");
         else printf("%d\n", pq.top()), pq.pop();
      }
      else pq.push(d);
   }
   return 0;
}
cs


>> 종만북을 많이 참고한 코드라고 한다.

<7-5> DP - 악수 (HandShaking)

PS/Topcoder training2018. 7. 4. 00:43

### DP ###

### SRM363 Div2 Level 2 ###


<소스코드>


d[i] : n 명이 하는 악수가 성립하는 조합의 수.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <cstdio>
 
long long d[51];
 
class HandsShaking {
public:
    long long countPerfect(int n) {
        long long *ret = &d[n];
        if(n < 2) return 1;
        if(n == 2) return 1;
        if(*ret) return *ret;
 
        for(int i=0; i<=n-2; i+=2) {
            *ret += (countPerfect(i)*countPerfect(n-2-i));
        }
        
        return *ret;
    }
};
 

cs


>> 이번 문제에서 나온 수를 카탈란 수 라고 한다...

'PS > Topcoder training' 카테고리의 다른 글

<8-4> 그리디 - 배치 시스템 (BatchSystem)  (0) 2018.07.16
<8-1> 탐색범위 한정 - 다양한 색상의 상자와 공 (ColorfulBoxesAndBalls)  (0) 2018.07.14
<5-7> 전체탐색 - 고장난 로봇 (CrazyBot)  (0) 2018.07.03
<5-4> 전체탐색 - 회문 (ThePalindrome)  (0) 2018.07.01
<7-4> DP - 킹 나이트 체스 (ChessMetric)  (0) 2018.07.01

<5-7> 전체탐색 - 고장난 로봇 (CrazyBot)

PS/Topcoder training2018. 7. 3. 00:55

### 전체탐색 ###

### SRM425 Div2 Level2 ###



<소스코드>


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
41
42
43
44
45
#include <vector>
using namespace std;
 
int visited[50][50];
int dr[]={0, 0, 1, -1};
int dc[]={1, -1, 0, 0}; // E W S N
int stack[20];
 
class CrazyBot {
public:
    int n;
    int dir[4];
    double ans;
    void dfs(int cnt, int r, int c) {
        if(cnt == n) {
            double tmp=1.0;
            for(int i=0; i<n; i++) {
                tmp *= (double)dir[stack[i]]/100;
            }
            ans += tmp;
            return ;
        }
        visited[r][c] = 1; 
        
        for(int k=0; k<4; k++) {
            int nr = r+dr[k];
            int nc = c+dc[k];
            if(!visited[nr][nc]) {
                stack[cnt] = k;
                dfs(cnt+1, nr, nc);
            }
        }
        visited[r][c] = 0; 
    }
 
    double getProbability(int n, int east, int west, int south, int north) {
        this->n = n;
        dir[0] = east; dir[1] = west;
        dir[2] = south; dir[3] = north;
        ans = 0;
        dfs(0, 25, 25); 
        return ans;
    }
};
 
cs


>> n의 최대값이 14이므로 50x50 개의 판을 가정하고 그의 가운데인 (25,25)에서 로봇이 이동하기 시작한다고 생각하였다.

>> 성공적으로 보행할 확률은 이동할 수 있는 모든 경우의 수에 해당하는 확룰을 더하면 된다.

'PS > Topcoder training' 카테고리의 다른 글

<8-1> 탐색범위 한정 - 다양한 색상의 상자와 공 (ColorfulBoxesAndBalls)  (0) 2018.07.14
<7-5> DP - 악수 (HandShaking)  (0) 2018.07.04
<5-4> 전체탐색 - 회문 (ThePalindrome)  (0) 2018.07.01
<7-4> DP - 킹 나이트 체스 (ChessMetric)  (0) 2018.07.01
<7-3> DP - 나쁜 이웃집 사람들 (BadNeighbors)  (0) 2018.07.01

<5-4> 전체탐색 - 회문 (ThePalindrome)

PS/Topcoder training2018. 7. 1. 21:39

### 전체탐색 ###

### SRM428 Div2 Level 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
#include <string>
using namespace std;
 
class ThePalindrome {
public:
    bool isP(char *str, int s, int e) {
        if(s >= e) return 1;
        return str[s]==str[e] ? isP(str, s+1, e-1) : 0;
    }
    int find(string s) {
        char str[101]={0};
        int size = s.size();
        for(int i=0; i<size; i++)
            str[i] = s[i];
        for(int i=0; i<size; i++) {
            if(isP(str, 0, size-1+i)) return size+i;
            for(int j=0; j<=i; j++) {
                str[size+i-j] = str[j];
            }
        }
        return size*2-1;
    }
};
 
cs


'PS > Topcoder training' 카테고리의 다른 글

<7-5> DP - 악수 (HandShaking)  (0) 2018.07.04
<5-7> 전체탐색 - 고장난 로봇 (CrazyBot)  (0) 2018.07.03
<7-4> DP - 킹 나이트 체스 (ChessMetric)  (0) 2018.07.01
<7-3> DP - 나쁜 이웃집 사람들 (BadNeighbors)  (0) 2018.07.01
<7-2> DP - 회사 조직과 급여 (CorporationSalary)  (0) 2018.07.01

<7-4> DP - 킹 나이트 체스 (ChessMetric)

PS/Topcoder training2018. 7. 1. 15:09

### DP ###

### TopCoder Collegiate Challenge 2003 Round 4 Div 1 Level 1 ###


 <소스코드>


- d[r][c][rest] : (r, c) 에서 (er, ec) 까지 rest 번만에 갈 수 있는 방법의 수


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
41
42
43
44
45
46
47
48
#include <vector>
#include <cstring>
using namespace std;
 
int n, er, ec;
int dr[] = {-1, -1, -1, 0, 0, 1, 1, 1, -2, -2, -1, 1, 2, 2, 1, -1};
int dc[] = {1, 0, -1, 1, -1, 1, 0, -1, 1, -1, -2, -2, -1, 1, 2, 2};
 
long long d[101][101][51];
 
bool safe(int r, int c)
{
    return (0 <= r && r < n) && (0 <= c && c < n);
}   
 
long long solve(int r, int c, int rest)
{
    long long *ret = &d[r][c][rest];
 
    if(rest == 0) {
        if(r == er && c == ec) return 1LL;
        return 0LL;
    }
    if(*ret != -1) return *ret;
 
    *ret = 0LL;
    for(int k=0; k<16; k++) {
        int nr = r+dr[k];
        int nc = c+dc[k];
        if(safe(nr, nc)) {
            *ret += solve(nr, nc, rest-1);
        }
    }
    return *ret;
}
 
class ChessMetric {
public:
    long long howMany(int size, vector<int> start, vector<int> end, int numMoves) {
        int sr = start[0];
        int sc = start[1];
        er = end[0]; ec = end[1];
        n = size;   
        
        memset(d, -1, sizeof(d));
        return solve(sr, sc, numMoves);
    }
};
cs


'PS > Topcoder training' 카테고리의 다른 글

<7-5> DP - 악수 (HandShaking)  (0) 2018.07.04
<5-7> 전체탐색 - 고장난 로봇 (CrazyBot)  (0) 2018.07.03
<5-4> 전체탐색 - 회문 (ThePalindrome)  (0) 2018.07.01
<7-3> DP - 나쁜 이웃집 사람들 (BadNeighbors)  (0) 2018.07.01
<7-2> DP - 회사 조직과 급여 (CorporationSalary)  (0) 2018.07.01

<7-3> DP - 나쁜 이웃집 사람들 (BadNeighbors)

PS/Topcoder training2018. 7. 1. 12:37

### DP ###


### 2004 TCCC Online Round 4 Div 1 Level 1 ###


<소스코드>


- d[i][j][k] : i번째 차례, j == 0 이면 이전 이웃에게 기부를 받음, k == 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
27
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
 
int d[41][2][2];
 
class BadNeighbors {
public:
    int n;
    int donation(vector<int> &donations, int i, bool prev, bool first) {
        int *ret = &d[i][prev][first];
        if(first && i == n-1) return 0;
        if(!first && i == n) return 0;
        if(*ret) return *ret;
        
        *ret = donation(donations, i+1, 0, first);
        if(!prev) *ret = max(*ret, donation(donations, i+1, 1, first)+donations[i]);
        return *ret;
    }
 
    int maxDonations(vector<int> donations) {
        n = donations.size();
        int ans = donation(donations, 1, 1, 1)+donations[0];
        return max(ans, donation(donations, 1, 0, 0));
    }
};
cs


>> first 가 1 이면 마지막 집은 n-2 번째 집이 되고, first 가 0이면 마지막 집은 n-1번째 집이 된다. (첫번째 집이 0번째 집이라고 생각)



<해설 소스코드>

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
#include <vector>
using namespace std;
 
class BadNeighbors {
public:
    int maxDonations(vector<int> donations) {
        int i;
        int ans = 0;
 
        int N = donations.size();
        int *dp = new int[N];
 
        for(i=0; i<N-1; i++) {
            dp[i] = donations[i];
            if(i > 0) dp[i] = max(dp[i], dp[i-1]);
            if(i > 1) dp[i] = max(dp[i], dp[i-2]+donations[i]);
            ans = max(ans, dp[i]);
        }
 
        for(i=0; i<N-1; i++) {
            dp[i] = donations[i+1];
            if(i > 0) dp[i] = max(dp[i], dp[i-1]);
            if(i > 1) dp[i] = max(dp[i], dp[i-2]+donations[i+1]);
            ans = max(ans, dp[i]);
        }
 
        delete []dp;
        return ans;
    }
};
 
cs


'PS > Topcoder training' 카테고리의 다른 글

<7-5> DP - 악수 (HandShaking)  (0) 2018.07.04
<5-7> 전체탐색 - 고장난 로봇 (CrazyBot)  (0) 2018.07.03
<5-4> 전체탐색 - 회문 (ThePalindrome)  (0) 2018.07.01
<7-4> DP - 킹 나이트 체스 (ChessMetric)  (0) 2018.07.01
<7-2> DP - 회사 조직과 급여 (CorporationSalary)  (0) 2018.07.01

<7-2> DP - 회사 조직과 급여 (CorporationSalary)

PS/Topcoder training2018. 7. 1. 11:06

### DP ###


### SRM407 Div2 Level 2 ###



<소스코드>


- d[i] : i번 매니저의 부하직원들에 대한 salary의 합.

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
#include <vector>
#include <algorithm>
using namespace std;
 
class CorporationSalary {
public:
    vector<int> child[51];
    long long d[51];
 
    long long salary(int k) {
        if(child[k].size() == 0) return 1;
        if(d[k]) return d[i];
 
        long long ret = 0LL;
        for(int i=0; i<child[k].size(); i++)
            ret += salary(child[k][i]);
        return d[k] = ret;
    }
 
    long long totalSalary(vector<string> relations) {
 
        for(int i=0; i<relations.size(); i++) {
            d[i] = 0;
            for(int j=0; j<relations[i].size(); j++) {
                if(relations[i][j] == 'Y')
                    child[i].push_back(j);
            }
        }
 
        long long ans = 0LL;
        for(int i=0; i<relations.size(); i++)
            ans += salary(i);
        return ans;
    }
};
 
cs


'PS > Topcoder training' 카테고리의 다른 글

<7-5> DP - 악수 (HandShaking)  (0) 2018.07.04
<5-7> 전체탐색 - 고장난 로봇 (CrazyBot)  (0) 2018.07.03
<5-4> 전체탐색 - 회문 (ThePalindrome)  (0) 2018.07.01
<7-4> DP - 킹 나이트 체스 (ChessMetric)  (0) 2018.07.01
<7-3> DP - 나쁜 이웃집 사람들 (BadNeighbors)  (0) 2018.07.01

티스토리툴바