문제 링크 : https://www.acmicpc.net/problem/2839


해결 방법)


Nkg 무게를 5kg과 3kg봉지로 최소로 가져가야 됬기에 5kg을 기준으로 최대 많이가져갈 수 있는 N/5 부터 0(5kg없는거) 까지의

모든 경우의 수를 제시하고 그에따라 3kg 봉지로 나눴을때 나머지가 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
#include<stdio.h>
int main()
{
    int five;
    int three;
    int i;
    int tmp;
    int base;
    scanf("%d",&base);
    
    for(i = (base/5); i>=0; i--)
    {
        tmp = base;
        tmp = tmp -(i*5);
        if(tmp % 3 == 0)
        {
            three = tmp / 3;
            printf("%d\n",i+three);
            break;
        }
    }
    if(i <0)
    {
        printf("-1");
    }
}
cs


반응형

'PS > 백준' 카테고리의 다른 글

2448번 별 찍기 - 11  (0) 2018.11.12
1966번 프린터 큐  (0) 2018.10.28
7576번 토마토  (0) 2018.10.24
14891번 톱니바퀴  (0) 2018.10.15
15686번 치킨 배달  (0) 2018.10.14

문제 링크 : https://www.acmicpc.net/problem/14891


해결방법)

문제를 읽고나서 생각해 봣는데 각 명령마다 순차적으로 톱뉘를 돌려나가면 되겠다라고 생각했다.

즉, 단순구현으로 풀었고(소스가 더러운느낌,..) 톱니번호와 회전방향을 가지고 있는 그대로 코드를 짜보았다.


- 알고리즘 순서 

1. 톱니 바퀴 정보를 입력받는다.

2. 각 명령을 하기 직전에 톱니들 사이의 접합부분이 맞닿았는지 혹은 떨어졌는지를 확인한다

3. 명령마다 주어진 바퀴번호와 회전방향을 보면서 해당 바퀴번호 기준으로 접합정보를 차례대로 비교해 나가면서 바퀴를 회전 시켜준다.

4. 명령이 끝날때까지 2,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
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
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
#include<iostream>
#include<cstring>
#define LEFT 6
#define RIGHT 2
using namespace std;
int cnt_cmd;
int wheel[4][8]; // 바퀴 0, 1, 2, 3
// 0 1 2 3 4 로 0은 12시방향 
int flag[4]; // 4바퀴의 회전여부 
void Check(int wheel[][8])
{
    if (wheel[0][RIGHT] == wheel[1][LEFT])
    {
        flag[0] = -1;
    }
    else
    {
        flag[0] = 1;
    }
    if (wheel[1][RIGHT] == wheel[2][LEFT])
    {
        flag[1] = -1;
    }
    else
    {
        flag[1] = 1;
    }
    if (wheel[2][RIGHT] == wheel[3][LEFT])
    {
        flag[2] = -1;
    }
    else
        flag[2] = 1;
 
}
void moveLeft(int wheel[][8] , int wheelnum)
{
    int tmp = wheel[wheelnum][RIGHT];
    for (int i = 3; i <= 7; i++)
    {
        wheel[wheelnum][i - 1] = wheel[wheelnum][i];
    }
    wheel[wheelnum][7] = wheel[wheelnum][0];
    wheel[wheelnum][0] = wheel[wheelnum][1];
    wheel[wheelnum][1] = tmp;
}
void moveRight(int wheel[][8] , int wheelnum)
{
    int tmp = wheel[wheelnum][LEFT];
    for (int i = 5; i >= 0; i--)
    {
        wheel[wheelnum][i + 1] = wheel[wheelnum][i];
    }
    wheel[wheelnum][0] = wheel[wheelnum][7];
    wheel[wheelnum][7] = tmp;
}
int main()
{
    for (int j = 0; j < 8; j++)
    {
        scanf("%1d", &wheel[0][j]);
    }
    for (int j = 0; j < 8; j++)
    {
        scanf("%1d", &wheel[1][j]);
    }
    for (int j = 0; j < 8; j++)
    {
        scanf("%1d", &wheel[2][j]);
    }
    for (int j = 0; j < 8; j++)
    {
        scanf("%1d", &wheel[3][j]);
    }
    /*for (int i = 0; i < 4; i++)
    {
        for (int j = 0; j < 8; j++)
        {
            printf("%d ", wheel[i][j]);
        }
        puts("");
    }*/
    cin >> cnt_cmd;
    int select, dir;
    int ret = 0;
    int tmp;
    for (int i = 0; i < cnt_cmd; i++)
    {
        scanf("%d %d", &select, &dir);
        memset(flag, 0, sizeof(flag));
        // 한번의 명령 마다 12시 방향값들을 더해나간다.
 
        Check(wheel);
        if (select == 1)
        {
            // 1번 바퀴일때 
            if (dir == -1)
            {
                moveLeft(wheel, 0);
                if (flag[0] == 1) // 다르다면 회전한다.
                {
                    //반시계일때
                    moveRight(wheel, 1);
                    if (flag[1] == 1)
                    {
                        moveLeft(wheel, 2);
                        if (flag[2] == 1)
                        {
                            moveRight(wheel, 3);
                        }
                    }
                }
            }
            else if (dir == 1)
            {
                //시계일때
                moveRight(wheel, 0);
                if (flag[0] == 1) // 다르다면 회전한다.
                {
                    moveLeft(wheel, 1);
                    if (flag[1] == 1)
                    {
                        moveRight(wheel, 2);
                        if (flag[2] == 1)
                        {
                            moveLeft(wheel, 3);
                        }
                    }
                }
            }
        }
        else if (select == 2)
        {
            if (dir == -1)
            {
                moveLeft(wheel, 1); // 두번째바퀴 시계반대돌리고
                if (flag[0] == 1)
                {
                    moveRight(wheel, 0); // 첫번째바퀴 시계방향돌린다.
                }
                if (flag[1] == 1)
                {
                    moveRight(wheel, 2);
                    if (flag[2] == 1)
                    {
                        moveLeft(wheel, 3);
                    }
                }
            }
            else if (dir == 1)
            {
                moveRight(wheel, 1);
                if (flag[0] == 1)
                {
                    moveLeft(wheel, 0);
                }
                if (flag[1] == 1)
                {
                    moveLeft(wheel, 2);
                    if (flag[2] == 1)
                    {
                        moveRight(wheel, 3);
                    }
                }
            }
        }
 
 
        else if (select == 3)
        {
            if (dir == -1)
            {
                moveLeft(wheel, 2);
                if (flag[1] == 1)
                {
                    //왼쪽이 달라서 돌릴수잇다면 
                    moveRight(wheel, 1);
                    if (flag[0] == 1)
                    {
                        moveLeft(wheel, 0);
                    }
                }
                if (flag[2] == 1)
                {
                    moveRight(wheel, 3);
                }
            }
            else if (dir == 1)
            {
                moveRight(wheel, 2);
                if (flag[1] == 1)
                {
                    moveLeft(wheel, 1);
                    if (flag[0] == 1)
                    {
                        moveRight(wheel, 0);
                    }
                }
                if (flag[2] == 1)
                {
                    moveLeft(wheel, 3);
                }
            }
        }
        else if (select == 4)
        {
            if (dir == -1)
            {
                moveLeft(wheel, 3);
                if (flag[2] == 1)
                {
                    moveRight(wheel, 2);
                    if (flag[1] == 1)
                    {
                        moveLeft(wheel, 1);
                        if (flag[0] == 1)
                        {
                            moveRight(wheel, 0);
                        }
                    }
                }
            }
            else if (dir == 1)
            {
                moveRight(wheel, 3);
                if (flag[2] == 1)
                {
                    moveLeft(wheel, 2);
                    if (flag[1] == 1)
                    {
                        moveRight(wheel, 1);
                        if (flag[0] == 1)
                        {
                            moveLeft(wheel, 0);
                        }
                    }
                }
            }
        }
 
    }
    ret = 0;
    if (wheel[0][0] == 1)ret += 1;
    if (wheel[1][0] == 1)ret += 2;
    if (wheel[2][0] == 1)ret += 4;
    if (wheel[3][0] == 1)ret += 8;
 
    cout << ret << '\n';
}
cs


반응형

'PS > 백준' 카테고리의 다른 글

2448번 별 찍기 - 11  (0) 2018.11.12
1966번 프린터 큐  (0) 2018.10.28
7576번 토마토  (0) 2018.10.24
2839 설탕배달  (0) 2018.10.19
15686번 치킨 배달  (0) 2018.10.14

문제 링크 : https://www.acmicpc.net/problem/15686


해결 방법)


풀고나서 다른 해결방법들을 보니까 대게 비슷하게 푼것같다. 

그래도 내가 푼 아이디어를 풀어보고자 한다. (누군가에게는 도움이 되겟지하는 생각에)

치킨집 고르는 경우 즉 M개(1개의 치킨집, 2개의 치킨집, 3개의 치킨집 ...... M개의 치킨집) 에서 모든 집들과의 거리중 최소거리만 구하여 이 최소거리의 합들이 우리가 구하고자하는 도시의 치킨거리값이 되는 것이다.


그런데 우리는 1개를 어떻게고르고 2개를 어떻게고르고에 대한 아이디어가 없당 ㅜ 이것은 재귀적으로 상황을 두개 만들어 주면 된다. 있고, 없고의 두가지상황인데 A,B,C의 치킨집이있다고하면,

A 있고 B 있고, C 없고

A 없고 B 있고 C 없고 .... 요론식으로 하다보면 모든 경우의수를 찾을 수 있다는 느낌을 받을 수 있다.

즉 각 치킨집마다 있고 없고의 상황 두가지를 만들어서 치킨집을 먼저 고를 수 있다.


이제 골라진 치킨집이 1개일때,2개일때 ,3개일때, 4개일때..... M개 이하 일때 마다 치킨 거리 총합을 알아야지 도시의 치킨거리를 알 수 가있는데 어떻게 골라진 치킨집 개수마다 그 치킨거리 총합을 알아낼 것인가가 문제이다.


이 해결방법은 모든 집마다 거리를 구하는데 골라진 집들과의 사이를 구하면서 최소값을 각 집마다 구해나가는 것이다.

우리는 각치킨집마다 경우를 있고,없고의 두가지 경우를 만들었는데, 이때 치킨집이 있다라면 이 치킨집은 골라진녀석이고 따로 골라졌다라는 표식을 남겨두면 나중에 골라진 치킨집에대해 거리값을 구해나갈수 있다.

따라서 골라진 치킨집과 모든 집들사이의 거리를 구할 수 있게되고 당연히 최소값도 구하게되면서 이 최소값들의 총합이 결국엔 우리가 구하는 답이 된다.


또 참고로 최대 M개라고해서 M개를 골랐을때만 왜 조건을 거냐라고 말할 수 있는데, 어차피 FOR문을 돌면 각집이 치킨집들 중 최소값만 지니기 때문에 하나의 치킨집만 선택된경우도 자연스레 포함이 되어 모든 경우를 내포하기때문이다.


소스코드)


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
#include<iostream>
#include<vector>
#include<cmath>
using namespace std;
int ans = 987654321; // 도시의 치킨거리
int M;
int visit[13];
vector<pair<int, int>> home; // 집좌표
vector<pair<int, int>> chicken; // 치킨 좌표
int csize;
int min(int a, int b) { return a < b ? a : b; }
void solve(int inow, int cnt_now)
{
    if (cnt_now == M) // 최대 M개를 고를때
    {
        int d; // 두점사이의 거리
        int x1, x2;
        int y1, y2;
        int tmp = 0;
        int homesize = home.size();
        for (int i = 0; i < homesize; i++)
        {
            int minnum = 987654321;
            for (int j = 0; j < csize; j++)
            {
                if (visit[j]) 
                {
                    d = abs(home[i].first - chicken[j].first) + abs(home[i].second - chicken[j].second);
                    if (minnum > d)
                        minnum = d;
                }
            }
            tmp += minnum;
            
        }
        ans = min(ans, tmp); //도시치킨거리 갱신
        return;
    }
    if (inow >= csize) return; 
    visit[inow] = 1;// 현재 치킨집 선택
    solve(inow + 1, cnt_now + 1); 
    visit[inow] = 0; 
    solve(inow + 1, cnt_now);
}
int main()
{
    int N;
    int num;
    cin >> N >> M;
    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= N; j++)
        {
            scanf("%d", &num);
            if (num == 1)
            {
                home.push_back({ i,j });
            }
            else if (num == 2)
            {
                chicken.push_back({ i,j });
            }
        }
    }
    csize = chicken.size();
    solve(0, 0);
    printf("%d\n",ans);
}
cs


반응형

'PS > 백준' 카테고리의 다른 글

2448번 별 찍기 - 11  (0) 2018.11.12
1966번 프린터 큐  (0) 2018.10.28
7576번 토마토  (0) 2018.10.24
2839 설탕배달  (0) 2018.10.19
14891번 톱니바퀴  (0) 2018.10.15

+ Recent posts

티스토리툴바