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



시뮬레이션 문제였다.


문제에서 하라는대로 해서 풀었다.


청소한 칸은 지도에 2로 표시하고 청소가 종료된 후 마지막에 값이 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
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;
 
int n, m, y, x, drec, cnt=0;
int map[50][50];
int dy[] = { -1,0,1,0 };
int dx[] = { 0,1,0,-1 };
 
void clean() {
    while (true) {
        //1.현재 위치 청소
        map[y][x] = 2;
        //모든방향 봄.
        int ny, nx;
        bool clearPossible = false;
        for (int i = 0; i < 4; i++) {
            ny = y + dy[i];
            nx = x + dx[i];
            if (map[ny][nx] == 0)
                clearPossible = true;
        }
        // 청소불가
        if (clearPossible == false) {
            int rd = (drec + 2) % 4;
            ny = y + dy[rd];
            nx = x + dx[rd];
            //벽
            if (map[ny][nx] == 1) {
                break;
            }
            else {
                y = ny;
                x = nx;
                continue;
            }
        }
 
        else {
            //왼쪽 봄.
            if (drec == 0)
                drec = 3;
            else
                drec--;
            
            ny = y + dy[drec];
            nx = x + dx[drec];
 
            if (map[ny][nx] == 0) {
                y = ny;
                x = nx;
            }
            continue;
        }
    }
}
 
int main()
{
    cin >> n >> m >> y >> x >> drec;
 
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            cin >> map[i][j];
 
    clean();
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (map[i][j] == 2)
                cnt++;
        }
    }
 
    cout << cnt;
 
}
cs


저작자표시

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

백준 14889번 스타트와 링크  (0) 2019.04.28
백준 14890번 경사로  (0) 2019.04.28
백준 14888번 연산자 끼워넣기  (0) 2019.04.27
백준 14500번 테트로미노  (0) 2019.04.26
백준 13460번 구슬 탈출 2  (0) 2019.03.08


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



완전탐색으로 풀었다.


가능한 연산자 조합의 경우를 모두 계산해보고 그 중 최소값과 최대값을 체크하여 마지막에 출력하였다.




소스코드


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>
 
using namespace std;
 
int a[11];
int oper[4];
int minNum = 1000000001, maxNum = -1000000001;
 
int oprtn(int fir, int oper, int sec) {
    switch (oper)
    {
    case 0:
        return fir + sec;
    case 1:
        return fir - sec;
    case 2:
        return fir * sec;
    case 3:
        if (fir < 0) {
            int tmp = fir * -1;
            tmp = tmp / sec;
            return tmp * -1;
        }
        else {
            return fir / sec;
        }
    default:
        break;
    }
}
 
void recur(int fir, int secIndex, int toPick) {
    if (toPick == 0) {
        if (fir > maxNum)
            maxNum = fir;
        if (fir < minNum)
            minNum = fir;
        return;
    }
 
    for (int i = 0; i < 4; i++) {
        if (oper[i] == 0) continue;
 
        oper[i]--;
        int ans = oprtn(fir, i, a[secIndex]);
        recur(ans, secIndex + 1, toPick - 1);
        oper[i]++;
    }
}
 
int main()
{
    int n;
 
    cin >> n;
 
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
 
    for (int i = 0; i < 4; i++) {
        cin >> oper[i];
    }
 
    recur(a[0], 1, n - 1);
 
    cout << maxNum << "\n" << minNum;
}
cs



저작자표시

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

백준 14890번 경사로  (0) 2019.04.28
백준 14503번 로봇 청소기  (0) 2019.04.27
백준 14500번 테트로미노  (0) 2019.04.26
백준 13460번 구슬 탈출 2  (0) 2019.03.08
백준 2407 조합  (0) 2019.02.26

 

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

 

14500번: 테트로미노

폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 꼭짓점끼리 연결되어 있어야 한다. 즉, 변과 꼭짓점이 맞닿아있으면 안 된다. 정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 다음과 같은 5가지가 있다. 아름이는 크기가 N×M인 종이 위에 테트로미노 하나를 놓으려고 한다. 종이는 1×1 크기의 칸으로 나누어

www.acmicpc.net

 

 

처음엔 대칭도 가능하다는 것을 못보고 맞왜틀 하고있었는데

대칭이 가능하단걸 알고 추가 해주니 맞았다.

 

문제 접근

1. 3차원배열에 가능한 테트노미로의 모양을 다 저장해놓았다.

 ttrmn[19][5][2]

- 19 : 가능한 도형의 모양 9개

- 5 : 블럭4개 + 그 도형의 세로, 가로길이를 넣어줄 마지막 인덱스 1개

- 2 : y좌표, x좌표

 

2. 반복문으로 모든 경우의 수의 합을 구하고 그중 가장 큰 값 출력하였다.

 

 

 

소스코드

#include <iostream>

 

using namespace std;

 

int n, m, max_sum = 0;

int map[500][500];

 

int ttrmn[19][5][2] = {

 

{ {0,0}, {0,1}, {1,0}, {1,1}, {2,2} },

 

{ {0,0}, {0,1}, {0,2}, {0,3}, {1,4} },

{ {0,0}, {1,0}, {2,0}, {3,0}, {4,1} },

 

{ {0,0}, {1,0}, {2,0}, {2,1}, {3,2} },

{ {0,0}, {0,1}, {0,2}, {1,0}, {2,3} },

{ {0,0}, {0,1}, {1,1}, {2,1}, {3,2} },

{ {0,2}, {1,0}, {1,1}, {1,2}, {2,3} },

 

{ {0,1}, {1,1}, {2,0}, {2,1}, {3,2} },

{ {0,0}, {1,0}, {1,1}, {1,2}, {2,3} },

{ {0,0}, {0,1}, {1,0}, {2,0}, {3,2} },

{ {0,0}, {0,1}, {0,2}, {1,2}, {2,3} },

 

{ {0,0}, {1,0}, {1,1}, {2,1}, {3,2} },

{ {0,1}, {0,2}, {1,0}, {1,1}, {2,3} },

{ {0,1}, {1,0}, {1,1}, {2,0}, {3,2} },

{ {0,0}, {0,1}, {1,1}, {1,2}, {2,3} },

 

{ {0,0}, {0,1}, {0,2}, {1,1}, {2,3} },

{ {0,1}, {1,0}, {1,1}, {2,1}, {3,2} },

{ {0,1}, {1,0}, {1,1}, {1,2}, {2,3} },

{ {0,0}, {1,0}, {1,1}, {2,0}, {3,2} }

 

};

 

int main()

{

    cin >> n >> m;

    

    for (int i = 0; i < n; i++) {

        for (int j = 0; j < m; j++) {

            cin >> map[i][j];

        }

    }

    

    for (int t = 0; t < 19; t++) {

        for (int i = 0; i < n - ttrmn[t][4][0] + 1; i++) {

            for (int j = 0; j < m - ttrmn[t][4][1] + 1; j++) {

                int sum = 0;

                for (int k = 0; k < 4; k++) {

                    sum += map[i + ttrmn[t][k][0]][j + ttrmn[t][k][1]];

                }

                if (max_sum < sum)

                    max_sum = sum;

            }

        }

    }

 

    cout << max_sum;

 

}

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

백준 14503번 로봇 청소기  (0) 2019.04.27
백준 14888번 연산자 끼워넣기  (0) 2019.04.27
백준 13460번 구슬 탈출 2  (0) 2019.03.08
백준 2407 조합  (0) 2019.02.26
백준 10974 모든 순열  (0) 2019.02.25


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



삼성 기출문제이다.


구현하는게 좀 짜증나는 문제였다.


dfs + 시뮬레이션으로 풀었다.


갈수있는 경우를 깊이우선으로 탐색하여 파란 구슬을 탈출하지 않고 빨간 구슬만 탈출하는 경우, 몇번만에 탈출하였는지 벡터에 저장 후 전체탐색이 끝나면 벡터의 값 중 가장 작은 값을 출력하여주었다.



아래는 소스코드이다.


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
#include <iostream>
#include <vector>
#include <string.h>
#include <algorithm>
using namespace std;
 
int m, n;
char map[10][10];
//상오하왼
int dy[] = { -1, 0, 1, 0 };
int dx[] = { 0, 1, 0, -1 };
 
vector<int> v;
 
// 정상졸료 0, 탈출 1
int move(int drt, int& ny, int& nx, int othy, int othx) {
    bool enemy = false;
    if (drt == 0) {
        //위로 이동
        if (othx == nx && othy < ny) {
            enemy = true;
        }
        for (int i = ny - 1; i > 0; i--) {
            if (enemy) {
                if (i == othy) break;
            }
            if (map[i][nx] != '.') {
                break;
            }
            ny--;
        }
        if (map[ny - 1][nx] == 'O') {
            ny = -1;
            nx = -1;
            return 1;
        }
        else
            return 0;
    }
    else if (drt == 1) {
        //오른쪽으로 이동
        if (othy == ny && othx > nx) {
            enemy = true;
        }
        for (int i = nx + 1; i < m - 1; i++) {
            if (enemy) {
                if (i == othx) break;
            }
            if (map[ny][i] != '.') {
                break;
            }
            nx++;
        }
        if (map[ny][nx + 1] == 'O') {
            ny = -1;
            nx = -1;
            return 1;
        }
        else
            return 0;
    }
    else if (drt == 2) {
        //아래로 이동
        if (othx == nx && othy > ny) {
            enemy = true;
        }
        for (int i = ny + 1; i < n - 1; i++) {
            if (enemy) {
                if (i == othy) break;
            }
            if (map[i][nx] != '.') {
                break;
            }
            ny++;
        }
        if (map[ny + 1][nx] == 'O') {
            ny = -1;
            nx = -1;
            return 1;
        }
        else
            return 0;
    }
    else if (drt == 3) {
        //왼쪽으로 이동
        if (othy == ny && othx < nx) {
            enemy = true;
        }
        for (int i = nx - 1; i > 0; i--) {
            if (enemy) {
                if (i == othx) break;
            }
            if (map[ny][i] != '.') {
                break;
            }
            nx--;
        }
        if (map[ny][nx - 1] == 'O') {
            ny = -1;
            nx = -1;
            return 1;
        }
        else
            return 0;
    }
    return 3;
}
 
void go(int ry, int rx, int by, int bx, int direction, int cnt) {
    if (cnt == 10) return;
 
    for (int d = 0; d < 4; d++) {
        int wry = ry;
        int wrx = rx;
        int wby = by;
        int wbx = bx;
 
        if (direction != -1 && (direction + 2) % 4 == d) continue;
        int nry = ry + dy[d];
        int nrx = rx + dx[d];
        bool rvs = false;
        
        if (d == 0) {
            if (rx == bx && by < ry) rvs = true;
        }
        else if (d == 1) {
            if (ry == by && bx > rx) rvs = true;
        }
        else if (d == 2) {
            if (rx == bx && by > ry) rvs = true;
        }
        else if (d == 3) {
            if (ry == by && bx < rx) rvs = true;
        }
 
        if (rvs) {
            //b움직, r움직, 탈출인지 확인, 재귀
            int br = move(d, wby, wbx, wry, wrx);
            int rr = move(d, wry, wrx, wby, wbx);
            if (br == 1) continue;
            if (br == 0 && rr == 1) {
                v.push_back(cnt + 1);
                continue;
            }
            go(wry, wrx, wby, wbx, d, cnt + 1);
        }
        else {
            //r움직, b움직, 탈출인지 확인, 재귀
            int rr = move(d, wry, wrx, wby, wbx);
            int br = move(d, wby, wbx, wry, wrx);
            if (br == 1) continue;
            if (br == 0 && rr == 1) {
                v.push_back(cnt + 1);
                continue;
            }
            go(wry, wrx, wby, wbx, d, cnt + 1);
        }
    }
 
}
 
 
int main()
{
    int fRy, fRx, fBy, fBx;
    char t;
    cin >> n >> m;
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> t;
            if (t == 'R') {
                fRy = i;
                fRx = j;
                map[i][j] = '.';
            }
            else if (t == 'B') {
                fBy = i;
                fBx = j;
                map[i][j] = '.';
            }
            else {
                map[i][j] = t;
            }
        }
    }
 
    go(fRy, fRx, fBy, fBx, -1, 0);
 
    if (v.size() == 0) cout << -1;
    else {
        int minr = 9999;
        for (int i = 0; i < v.size(); i++) {
            minr = min(minr, v[i]);
        }
        cout << minr;
    }
}
cs



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

백준 14888번 연산자 끼워넣기  (0) 2019.04.27
백준 14500번 테트로미노  (0) 2019.04.26
백준 2407 조합  (0) 2019.02.26
백준 10974 모든 순열  (0) 2019.02.25
백준 1764 듣보잡  (0) 2019.02.20


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


대충보고 쉬운 문제인줄 알고 생각없이 코딩하고 테케를 넣어봤는데 결과값이 너무 커서 자료형 범위를 넘어가서 답이 안나왔다.


할수 없이 오랜만에 이클립스를 켰다. 자바 만세.


BigInteger를 사용한 것 빼고는 뭐 그냥 조합공식을 코드로 옮기기만 하면 되는 문제이다.



아래는 소스코드이다.


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
import java.math.BigInteger;
import java.util.Scanner;
 
public class Main {
    
    public static void main(String[] args) {
        int n, m;
        BigInteger bm, bj;
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        
        bm = facto(n-m).multiply(facto(m));
        bj = facto(n);
        
        System.out.println(bj.divide(bm));
    }
    
    public static BigInteger facto(int a) {
        if(a==0) return BigInteger.valueOf(1);
        
        BigInteger ret = new BigInteger("1");
        for(int i=1; i<=a; i++) {
            ret = ret.multiply(BigInteger.valueOf(i));
        }
        return ret;
    }
}
cs






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

백준 14500번 테트로미노  (0) 2019.04.26
백준 13460번 구슬 탈출 2  (0) 2019.03.08
백준 10974 모든 순열  (0) 2019.02.25
백준 1764 듣보잡  (0) 2019.02.20
백준 1779번 비숍  (0) 2019.01.29


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


n이 작아서 재귀를 이용한 완전탐색으로 풀었다.




1. n을 입력받고,  pair<int, bool>가 들어갈 벡터 v를 선언하고 1~n까지 총 n개의 수를 벡터에 넣어주었다.

( pair의 first : 1~n까지의 정수 / pair의 second : 해당 정수를 선택했는지 여부 )


2. 재귀를 이용하여 완전탐색을 하였다.

for문으로 벡터v를 훑으면서 선택하지 않은 수가 있다면 선택하여 picked 벡터에 추가.

n개의 수를 모두 선택하였다면 벡터 picked 출력하고 함수 종료.




아래는 소스코드이다.


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
#include <iostream>
#include <vector>
using namespace std;
 
int n;
vector<pair<int, bool>> v;
vector<int> picked;
 
void pick(int toPick) {
    if (toPick == 0) {
        for (int i = 0; i < picked.size(); i++) {
            cout << picked[i] << " ";
        }
        cout << "\n";
        return;
    }
 
    for (int i = 0; i < n; i++) {
        if (v[i].second) continue;
 
        v[i].second = true;
        picked.push_back(v[i].first);
        pick(toPick - 1);
        v[i].second = false;
        picked.pop_back();
    }
}
 
int main()
{
    cin >> n;
 
    for(int i = 1; i <= n; i++) {
        v.push_back(make_pair(i, false));
    }
 
    pick(n);
}
cs





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

백준 13460번 구슬 탈출 2  (0) 2019.03.08
백준 2407 조합  (0) 2019.02.26
백준 1764 듣보잡  (0) 2019.02.20
백준 1779번 비숍  (0) 2019.01.29
백준 9663번 N-Queen  (0) 2019.01.28


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


두개의 벡터에 입력받아 하나하나 다 비교를 해보면 시간초과가 날것같아서 맵을 사용하여 풀었다.


1. 듣도못한 사람의 목록을 입력받아 map에 저장한다.

2. 보도못한 사람들의 목록을 입력받으며 map에 존재하는 이름인지 체크하고 존재한다면 벡터에 추가해준다.

3. 벡터를 sort해주고 벡터길이와 내용을 출력해준다.


맵은 처음 사용해봐서 너무 익숙치않았다.

다 풀고나서 같이 공부하는 동생의 소스를 봤는데 굳이 맵을 사용하지 않고 훨씬더 쉽게 풀어놨다.

비효윻적으로 푼것같지만 안써본 map을 써봤다는 것에 의미를 둬야겠다.


아래는 소스코드이다.




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>
#include <vector>
#include <map>
#include <string>
#include <algorithm>
using namespace std;
 
vector<string> v;
 
int main()
{
    int a, b;
    map<string, int> m;
    map<string, int>::iterator iter;
 
    cin >> a >> b;
 
    for (int i = 0; i < a; i++) {
        string tmp;
        cin >> tmp;
        m.insert(make_pair(tmp, 0));
    }
 
    for (int i = 0; i < b; i++) {
        string tmp;
        cin >> tmp;
        iter = m.find(tmp);
        if (iter != m.end()) {
            v.push_back(iter->first);
        }
    }
 
    cout << v.size() << "\n";
 
    sort(v.begin(), v.end());
 
    for (int i = 0; i < v.size(); i++) {
        cout << v[i] << "\n";
    }
}
cs









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

백준 2407 조합  (0) 2019.02.26
백준 10974 모든 순열  (0) 2019.02.25
백준 1779번 비숍  (0) 2019.01.29
백준 9663번 N-Queen  (0) 2019.01.28
백준 1325번 효율적인 해킹  (0) 2019.01.23


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


처음에 문제를 풀고 제출을 했을 때 시간 초과가 났다.

나름 잘 푼것 같은데 시간초과가 나서 왜인지 고민하다가 다른사람들의 답을 보았는데

체스판 흑영역과 백영역을 구분해서 탐색하는 방법으로 시간을 줄여야 했던거였다.

아마 혼자서 그 방법을 생각하려면 굉장히 많은 시간이 들었을것같다.


그런데 흑백으로 구분해서 풀고나니 틀렸습니다가 떴다.

아무리 생각해도 로직이 잘못된것 없는것같아서 맞왜틀맞왜틀 하고있었는데 배열사이즈를 넉넉하게 잡아주었더니 맞았다.



문제 접근


1. 비숍은 이동방향이 대각선이므로 하나의 대각선에는 하나의 비숍만이 위치해야한다.


2. 오른쪽 위로 향하는 대각선을 기준으로 잡고 0부터 2n-2까지의 대각선(0부터 시각하였으므로 총 2n-1개의 대각선)을 재귀함수를 통해 완전탐색을 하며 하나의 대각선 마다 비숍의 자리를 골라주었다.

 비숍을 선택하지 않고 대각선을 넘기는 경우도 고려 해주었다.

 오른쪽 아래로 향하는 대각선과의 중복을 확인해주기 위해 비숍을 놓을 때 decr배열에 표시를 해주었고, 비숍을 놓기전에 decr배열을 보고 놓을수 있는지 없는지를 판단하였다.


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
#include <iostream>
#include <algorithm>
using namespace std;
 
int n, maxR = 0;
int map[20][20];
bool decr[30];
 
void recur(int line, int picknum) {
    if (line >= 2 * n - 1) {
        maxR = max(maxR, picknum);
        return;
    }
 
    for (int y = 0; y <= line; y++) {
        int x = line - y;
        if (map[y][x] == 0 || decr[y - x + n - 1] == true) continue;
 
        decr[y - x + n - 1] = true;
        recur(line + 2, picknum + 1);
        decr[y - x + n - 1] = false;
    }
    recur(line + 2, picknum);
}
 
int main()
{
    int answer = 0;
    cin >> n;
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> map[i][j];
        }
    }
 
    recur(0, 0);
    answer += maxR;
 
    maxR = 0;
    recur(1, 0);
    answer += maxR;
 
    cout << answer << endl;
}
cs






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

백준 10974 모든 순열  (0) 2019.02.25
백준 1764 듣보잡  (0) 2019.02.20
백준 9663번 N-Queen  (0) 2019.01.28
백준 1325번 효율적인 해킹  (0) 2019.01.23
백준 2468번 안전영역  (0) 2019.01.22

+ Recent posts

티스토리툴바