Strong Root

Coin Change(COINS) 정답 코드

뿌리튼튼 CS/Algorithm2015. 2. 23. 18:04

난이도 ★★★☆☆


문제를 보시려면 여기를 클릭




힌트

 전형적인 동적계획법 문제

 → 완전 탐색 + 캐시 사용




이하는 코드입니다.


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
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <vector>
 
#define C_MAX 100
#define M_MAX 5000
#define MOD_AMOUNT 1000000007
 
#pragma warning(disable:4996)
 
using namespace std;
 
vector<int> coins;
int cache[M_MAX][C_MAX];
 
int getCount(int money, int maxCoinIndex) {
    int& ret = cache[money][maxCoinIndex];
    if (ret != -1) {
        return ret;
    }
 
    // case found
    if (money == 0) {
        return ret = 1;
    }
 
    // if this is a leaf node
    if (maxCoinIndex == 0) {
        if (money % coins[maxCoinIndex] == 0) {
            return ret = 1;
        }
 
        return ret = 0;
    }
 
    // non-leaf node
    ret = 0;
    for (int pSum = 0; pSum <= money; pSum += coins[maxCoinIndex]) {
        ret = (ret + getCount(money - pSum, maxCoinIndex - 1)) % MOD_AMOUNT;
    }
 
    return ret;
}
 
int main() {
    int T;
    scanf("%d\n", &T);
 
    while (T-- > 0) {
        // get M, C
        int M, C;
        scanf("%d %d", &M, &C);
 
        // get sorted coins
        coins.clear();
        for (int i = 0; i < C; i++) {
            int coin;
            scanf("%d", &coin);
            coins.push_back(coin);
        }
        sort(coins.begin(), coins.end());
 
        // solve and print
        memset(cache, -1, sizeof(cache));
        printf("%d\n", getCount(M, C - 1));
    }
 
    return 0;
}
cs

저작자표시 비영리 동일조건 (새창열림)

'뿌리튼튼 CS > Algorithm' 카테고리의 다른 글

짝맞추기(MEETING) 정답 코드  (0) 2015.02.26
달팽이(SNAIL) 정답 코드  (0) 2015.02.24
최소, 최대 정사각형 찾기 1(MMRECT1) 정답 코드  (0) 2015.02.16
Microwaving Lunch Boxes(LUNCHBOX) 정답 코드  (0) 2015.02.12
회전초밥(SUSHI) 정답 코드  (0) 2015.02.10

최소, 최대 정사각형 찾기 1(MMRECT1) 정답 코드

뿌리튼튼 CS/Algorithm2015. 2. 16. 17:23

난이도 ★★★★☆


문제를 보시려면 여기를 클릭




틀리기 쉬운 입출력 예제

입력

출력 

3

4

10000 -10000

-10000 10000

10000 10000

-10000 -10000

7

2 2

2 4

5 4

5 1

1 1

1 2

2 1

8

7 19

11 15

3 11

3 15

7 11

11 11

3 19

11 19

20000 20000

1 3

8 8




힌트

 정사각형을 만드는 네 점을 잡았다면, 그 네 점은 (x1, y1), (x1, y2), (x2, y1), (x2, y2) 이런 형태이다.

 → 따라서 같은 값이 하나도 없는 좌표는 탐색할 필요가 없다. 같은 값이 최소 1개 이상 있는 것만 탐색한다.



이하는 코드입니다. (내 생에 최다의 for문 중첩. 무려 7중)


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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
#include <stdio.h>
#include <vector>
#include <algorithm>
 
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) > (b)) ? (a) : (b))
 
#pragma warning(disable:4996)
 
using namespace std;
 
typedef struct {
    int x;
    int y;
}Point;
 
bool myCompareX(const vector<Point> left, const vector<Point> right) {
    return left[0].x < right[0].x;
}
 
bool myCompareY(const Point left, const Point right) {
    return left.y < right.y;
}
 
int main() {
    int T;
    scanf("%d\n", &T);
    
    while (T-- > 0) {
        int N;
        scanf("%d", &N);
 
        // get points
        vector<vector<Point>> points;
        for (int i = 0; i < N; i++) {
            Point *point = new Point;
 
            scanf("%d %d", &point->x, &point->y);
 
            bool found = false;
            for (int j = 0; j < points.size(); j++) {
                if ((points[j].size() > 0) && (points[j][0].x == point->x)) {
                    points[j].push_back(*point);
                    found = true;
                    break;
                }
            }
            
            if (!found) {
                vector<Point> *arr = new vector<Point>;
                arr->push_back(*point);
                points.push_back(*arr);
            }
        }
 
        // trim
        for (int i = 0; i < points.size(); i++) {
            if (points[i].size() < 2) {
                points.erase(points.begin() + i);
            }
        }
 
        // sort
        for (int i = 0; i < points.size(); i++) {
            sort(points[i].begin(), points[i].end(), myCompareY);
        }
        sort(points.begin(), points.end(), myCompareX);
 
        /* find min, max */
        int minLength = 20001, maxLength = 0;
 
        for (int i = 0; i < points.size() - 1; i++) {
            // get x
            for (int j = 0; j < points[i].size() - 1; j++) {
                // (x, y1)
                int y1 = points[i][j].y;
                for (int k = j + 1; k < points[i].size(); k++) {
                    // (x, y2)
                    int y2 = points[i][k].y;
                    int length = y2 - y1;
                    int nextX = points[i][0].x + length;
 
                    // find nextX
                    for (int l = i + 1; l < points.size(); l++) {
                        // nextX found
                        if (points[l][0].x == nextX) {
                            for (int m = 0; m < points[l].size() - 1; m++) {
                                // y1 found
                                if (points[l][m].y == y1) {
                                    for (int n = m + 1; n < points[l].size(); n++) {
                                        // Finally, y2 found
                                        if (points[l][n].y == y2) {
                                            minLength = MIN(minLength, length);
                                            maxLength = MAX(maxLength, length);
                                            break;
                                        }
 
                                        // y2 not found
                                        if (points[l][n].y > y2) {
                                            break;
                                        }
                                    }
                                    break;
                                }
 
                                // y1 not found
                                if (points[l][m].y > y1) {
                                    break;
                                }
                            }
                            break;
                        }
 
                        // nextX not found
                        if (points[l][0].x > nextX) {
                            break;
                        }
                    }
                }
            }
        }
 
        // print
        printf("%d %d\n", minLength, maxLength);
    }
 
    return 0;
}
cs

저작자표시 비영리 동일조건 (새창열림)

'뿌리튼튼 CS > Algorithm' 카테고리의 다른 글

달팽이(SNAIL) 정답 코드  (0) 2015.02.24
Coin Change(COINS) 정답 코드  (0) 2015.02.23
Microwaving Lunch Boxes(LUNCHBOX) 정답 코드  (0) 2015.02.12
회전초밥(SUSHI) 정답 코드  (0) 2015.02.10
소풍(PICNIC) 정답 코드  (0) 2015.02.09

[강좌] 초급2 - 버튼 클릭 + 리스너

뿌리튼튼 CS/Android2015. 2. 15. 14:56

<초급1 - 입문 + xml, java 파일 작성법 바로가기>



다음으로 버튼(Button)을 배워보겠습니다.


아래와 같은 화면을 구성해보겠습니다.


[그림2-1] 목표2



먼저 기존의 xml 파일을 아래와 같이 수정합니다.


[그림2-2] activity_my.xml


위와 같이 xml 내용을 입력한 후 미리보기(preview)를 보시면 [그림2-1]와 같은 모습이 보입니다. 이제 뷰는 완성되었습니다.






Java 파일을 아래와 같이 수정합니다.


[그림2-3] MyActivity.java


여기까지 작성한 후 휴대폰을 pc에 연결하고 Run을 시켜봅니다.


어플이 실행되며...는 개뿔 컴파일 에러가 뜹니다. 죄송합니다 ㅎㅎ 코드 설명을 위해 잠깐 멈추었습니다.










[그림2-3]의 빨간 박스 안의 코드를 살펴보겠습니다.







바인딩(Binding)이라고 이름까지 있는 중요한 코드입니다.


xml 상의 뷰를 Java에서 컨트롤할 수 있도록 id값을 통해 말그대로 묶어주는(bind) 역할을 합니다.







위 그림처럼, 바인딩한 Java변수에 점(.)을 찍어보면 굉장히 많은 일들을 할 수 있다는 것을 알 수 있습니다.


xml에서 할 수 있는 일(가로 세로 크기 등)을 Java의 바인딩된 변수를 통해서도 할 수 있습니다.


이 바인딩의 가장 큰 장점은 런타임에서의 동적인 처리를 가능케 한다는 것입니다.







우리는 위 목록 중에서 setOnClickListener(OnClickListener l) 함수를 사용해보겠습니다.


위처럼 타이핑 해보면 괄호 안에 빨간 줄이 그이며 뷰에 등록할 OnClickListner 객체를 쓰라고 합니다.


여기에 OnClickListener 객체를 넣는 방법은 크게 두가지가 있습니다.


① 해당 객체를 그자리에서 new로 생성해주는 방법

② 현재 Activity 클래스 자신이 OnClickListener를 구현(implement)하고 자신(this)을 인자로 넘겨주는 방법


결론부터 말하면 ②가 좋습니다만 ①부터 살펴보겠습니다 ㅎㅎ




<① 해당 객체를 그자리에서 new로 생성해주는 방법>


보통 가장 처음으로 배우는 방법입니다.



위와 같이 코드를 작성하고 'do something' 자리에 하고 싶은 일을 적으면 됩니다.




이 방법은 굉장히 간편합니다. 단, 뷰가 하나일 때만요.


버튼이 두개 이상이라면 어떨까요?



뷰의 개수만큼 OnClickListener 객체를 새로 생성해주고 있습니다.


②를 볼까요?






<② 현재 Activity 클래스 자신이 OnClickListener를 구현(implement)하고 자신(this)을 인자로 넘겨주는 방법>





이해를 위해, 구현(implements)도 상속(extends)과 비슷하다고 보시면 좋습니다.




이렇게 쓰는 순간, MyActivity 자신이 OnClickListener 객체가 되게 됩니다.


즉, MyActivity는 Activity이면서 동시에 OnClickListener인겁니다.




따라서 OnClickListener 객체를 요하는 setOnClickListener() 함수에 자기 자신(this)을 인자로 넘겨주면 되는 것입니다.




보시면, 뷰의 개수가 늘어나도 OnClickListener 객체를 새로 생성하지 않습니다. 메모리가 조금이라도 덜 들어가겠죠.


또한 하나의 onClick()함수만 사용함으로써 코드의 가독성이 훨씬 증가합니다.










다시 본론으로 돌아가서 Java 파일을 완성해보겠습니다.


[그림2-4] MyActivity.java


위와 같이 작성한 후 휴대폰을 pc에 연결하고 Run을 시켜봅니다.


어플이 실행되며 xml 미리보기에서 봤던 것과 같은 화면이 여러분의 휴대폰에서 보일 것입니다.




'첫 버튼'을 클릭했을 때 '첫 토스트'가 뜬다면 성공입니다.










본격적인 안드로이드의 세계로 오신 것을 환영합니다. 


저작자표시 비영리 동일조건 (새창열림)

'뿌리튼튼 CS > Android' 카테고리의 다른 글

File to Byte Array (File을 Byte배열로 변환)  (0) 2015.06.12
Android Studio에서 Library 추가시 쓸데없는 Duplicate 오류 대처법  (0) 2015.06.12
[강좌] Android SDK Search - 설치 및 SDK 소스 보기  (0) 2015.01.17
[강좌] 초급1 - 입문 + xml, java 파일 작성법  (0) 2015.01.16
Intent 활용 예시  (0) 2014.11.12

Microwaving Lunch Boxes(LUNCHBOX) 정답 코드

뿌리튼튼 CS/Algorithm2015. 2. 12. 10:38

난이도 ★☆☆☆☆


문제를 보시려면 여기를 클릭



힌트

 오래 먹는 사람을 먼저 먹인다. 만약 먹는 시간이 같은 사람이 있다면 데우는 시간이 짧은 사람을 먼저 먹인다.

 → E를 내림차순으로 정렬, 동점자에 한해서 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
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
#include <stdio.h>
#include <queue>
 
#define MAX_N 10000
#define MAX(a ,b) (((a) > (b)) ? (a) : (b))
 
#pragma warning(disable:4996)
 
using namespace std;
 
typedef struct {
    int M;
    int E;
} LunchBox;
 
LunchBox lunchBoxes[MAX_N];
 
struct MaxCompare {
    bool operator() (const int index1, const int index2) {
        const LunchBox left = lunchBoxes[index1];
        const LunchBox right = lunchBoxes[index2];
 
        if (left.E == right.E) {
            return left.M > right.M;
        }
 
        return left.E < right.E;
    }
};
 
int main() {
    int T;
    scanf("%d\n", &T);
 
    while (T-- > 0) {
        int N;
        scanf("%d", &N);
 
        // get M
        int totalMTime = 0;
        for (int i = 0; i < N; i++) {
            scanf("%d", &lunchBoxes[i].M);
            totalMTime += lunchBoxes[i].M;
        }
 
        // get E and make heap
        priority_queue<int, vector<int>, MaxCompare> maxHeap;
        for (int i = 0; i < N; i++) {
            scanf("%d", &lunchBoxes[i].E);
            int *heapNode = new int;
            *heapNode = i;
            maxHeap.push(*heapNode);
        }
 
        //
        int time = 0;
        int tmpMTime = 0;
        int heapSize = maxHeap.size();
        for (int i = 0; i < heapSize; i++) {
            LunchBox top = lunchBoxes[maxHeap.top()];
 
            tmpMTime += top.M;
            time = MAX(time, top.E + tmpMTime);
 
            maxHeap.pop();
        }
 
        printf("%d\n", time);
    }
 
    return 0;
}
cs

저작자표시 비영리 동일조건 (새창열림)

'뿌리튼튼 CS > Algorithm' 카테고리의 다른 글

Coin Change(COINS) 정답 코드  (0) 2015.02.23
최소, 최대 정사각형 찾기 1(MMRECT1) 정답 코드  (0) 2015.02.16
회전초밥(SUSHI) 정답 코드  (0) 2015.02.10
소풍(PICNIC) 정답 코드  (0) 2015.02.09
0-1수열(ZEROONE) 정답 코드  (0) 2015.02.09

티스토리툴바