<링크>

https://www.acmicpc.net/problem/11580


<풀이>

HashMap의 Key는 x좌표, Value는 해당하는 x좌표에 나왔던 y좌표들의 Set이다.

배열을 이용해 이미 나왔던 좌표인지 체크할수도있지만

라이브러리한번 써보고 싶어서 이렇게 했다.


<소스코드>

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
import java.io.*;
import java.util.*;
 
public class Main {
    public static void main(String[] args) {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        HashMap<Integer, HashSet<Integer>> hm = new HashMap<>();
        try {
            br.readLine();
            String s = br.readLine();
            int x = 0, y = 0, ans = 1;
            HashSet<Integer> hs = new HashSet<>();
            hs.add(y);
            hm.put(x, hs);
 
            int len = s.length();
            for (int i = 0; i < len; ++i) {
                char c = s.charAt(i);
                switch (c) {
                case 'N':
                    ++y;
                    break;
                case 'S':
                    --y;
                    break;
                case 'W':
                    --x;
                    break;
                case 'E':
                    ++x;
                    break;
                }
                if (!hm.containsKey(x)) {
                    HashSet<Integer> tmp = new HashSet<>();
                    tmp.add(y);
                    hm.put(x, tmp);
                    ++ans;
                } else {
                    HashSet<Integer> tmp = hm.get(x);
                    if (!tmp.contains(y)) {
                        tmp.add(y);
                        ++ans;
                    }
                }
 
            }
            System.out.println(ans);
        } catch (IOException e) {
            // TODO Auto-generated catch block
            e.printStackTrace();
        }
 
    }
}
cs


저작자표시

'알고리즘 풀이 > 라이브러리' 카테고리의 다른 글

백준 1302 베스트셀러 :: 들짐승  (0) 2018.07.22
백준 10820 문자열 분석 :: 들짐승  (0) 2018.07.22

<링크>

https://www.acmicpc.net/problem/14890


<풀이>

시키는 대로 하면된다.
문제에 나와있는 조건을 구현하는데
모든 행을 쭉 봐야하고 모든 열을 또 봐야하기 때문에 처음부터 2차원 배열을 두 개를 만들었다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
for(int i=0;i<N;++i)
        for (int j = 0; j < N; ++j)
        {
            int n;
            scanf("%d", &n);
            h[i][j] = v[j][i] = n;
        }
 
.....
 
 
for (int i = 0; i < N; ++i)
    {
        ans += isValid(h[i]);
        ans += isValid(v[i]);
    }
cs

가로방향, 세로방향을 한번에 입력해놓고 각 행의 주소를 포인터 인자로 넘겨줘서 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
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
#include<stdio.h>
int h[100][100];
int v[100][100];
int N, L;
int isValid(int *);
int main()
{
    scanf("%d%d", &N, &L);
    for(int i=0;i<N;++i)
        for (int j = 0; j < N; ++j)
        {
            int n;
            scanf("%d", &n);
            h[i][j] = v[j][i] = n;
        }
    
    int ans = 0;
    for (int i = 0; i < N; ++i)
    {
        ans += isValid(h[i]);
        ans += isValid(v[i]);
    }
    printf("%d", ans);
}
int isValid(int *p)
{
    int installed[100] = { 0, };
    for (int i = 1; i < N; ++i)
    {
        if (p[i - 1] < p[i])
        {
            if (i - L < 0)
                return 0;
            int height = p[i]-1;
            for (int j = i - 1; j >= i - L; --j)
                if (height != p[j] || installed[j]) 
                    return 0;
            for (int j = i - 1; j >= i - L; --j)
                installed[j] = 1;
        }
        else if (p[i - 1] > p[i])
        {
            if (i + L-1>= N)
                return 0;
            int height = p[i - 1]-1;
            for (int j = i; j < i + L; ++j)
                if (height != p[j] || installed[j])
                    return 0;
            for (int j = i; j < i + L; ++j)
                installed[j] = 1;
 
        }
    }
    return 1;
}
cs


저작자표시

'알고리즘 풀이 > 시뮬레이션' 카테고리의 다른 글

백준 15685 드래곤커브  (0) 2018.09.30
백준 14499 주사위굴리기 :: 들짐승  (0) 2018.07.22
백준 3190 뱀 :: 들짐승  (0) 2018.07.22
백준 12100 2048(Easy) :: 들짐승  (0) 2018.07.22

<링크>

https://www.acmicpc.net/problem/14501


<풀이>

그냥 DFS로 풀어도 된다. i일에 일을 한다, 안한다로 나눠서 최대 2^15만큼의 시간이 걸리기 때문에 상관없다. 불필요한 재귀를 줄여보고자 DP로 풀었다. dp[i] 에는 i일부터 시작해서 벌수있는 최대 수익을 기록했다. 
예를 들어 4일부터 시작해서 벌수있는 최대금액을 dp[4]에 저장해놓으면 나중에 1일에, T1=3이라서 4일로 왔을때나 / 3일에, T3=1이라서 4일로 왔을때 4일부터 시작해서 끝까지 가보는 중복연산을 없앨 수 있다.
i일에서,
1.만약 짤리기 전까지 일을 할수있으면 일한 수익+일끝난 다음날부터 계산한값
2.오늘 일 안하고 내일로 패스하고 계산된값

중 최대값을 dp[i]에 저장하였다.

1은 i+T[i] <= N+1 의 조건을 만족해야하고
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
#include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std;
int T[16],int P[16],int dp[16],int N;
int recur(int);
int main()
{
    memset(dp, -1, sizeof(dp));
    scanf("%d", &N);
    for (int i = 1; i <= N; ++i)
        scanf("%d %d", T + i, P + i);
    printf("%d\n",recur(1));
}
int recur(int i)
{
    if (i == N + 1) return 0;
    int &ret = dp[i];
    if (ret != -1)
        return ret;
    int a = 0;
    if (i + T[i] <= N + 1)
        a = max(a, recur(i + T[i]) + P[i]);
    a=max(a,recur(i + 1));
    return ret = a;
}
cs


<피드백>

recur함수에서 기저점 우선순위를 잘못세팅해서 틀렸다고 떴었다.
처음에는

1
2
3
4
int &ret = dp[i];
if (ret != -1)
    return ret;
if (i == N + 1) return 0;
cs


이런 식으로 해놔서 퇴사 당일까지 왔을 때는 i가 N+1임에도 dp[N+1]에 접근하게 되고 개판이 됐었다.
이런 ㅄ같은 실수를 줄여야 한단계 성장할 수 있을 것 같아서 적었다.

저작자표시

'알고리즘 풀이 > DP' 카테고리의 다른 글

백준 9084 동전  (0) 2018.08.17
백준 1005 ACM Craft  (0) 2018.08.06
백준 9095 1,2,3 더하기  (0) 2018.07.26

<링크>

https://www.acmicpc.net/problem/14499


<풀이>

주사위를 하나 그려놓고 상하좌우로 굴려보며 규칙성을 찾았다.

주사위 평면도가 다음과 같으면
2면 : 배열[0]
4면 : 배열[1]
1면 : 배열[2]
3면 : 배열[3]
5면 : 배열[4]
6면 : 배열[5]
각각 면의 숫자를 배열 해당위치에 넣어준다. 처음엔 모두 0이다.
위로 굴리면 그림처럼 아랫방향으로 shift되고 4면 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
#include<stdio.h>
int dice[6] = { 0,0,0,0,0,0 };
int pan[20][20];
int N, M, x, y, K;
void east();
void west();
void north();
void south();
void check();
int main()
{
    scanf("%d%d%d%d%d", &N, &M,&x,&y,&K);
    for(int i=0;i<N;++i)
        for(int j=0;j<M;++j)
            scanf("%d", &pan[i][j]);
    while (K--)
    {
        int k;
        scanf("%d", &k);
        switch (k)
        {
        case 1:
            if (y + 1 < M)
            {
                east();
                ++y;
                check();
            }
            break;
        case 2:
            if (y - 1 >= 0)
            {
                west();
                --y;
                check();
            }
            break;
        case 3:
            if (x - 1 >= 0)
            {
                north();
                --x;
                check();
            }
            break;
        case 4:
            if (x + 1 < N)
            {
                south();
                ++x;
                check();
            }
            break;
        }
    }
}
void check()
{
    
    if (pan[x][y] == 0)
        pan[x][y] = dice[2];
    else
    {
        dice[2] = pan[x][y];
        pan[x][y] = 0;
    }
    printf("%d\n", dice[5]);
}
void east()
{
    int tmp = dice[1];
    dice[1] = dice[2];
    dice[2] = dice[3];
    dice[3] = dice[5];
    dice[5] = tmp;
}
void west()
{
    int tmp = dice[3];
    dice[3] = dice[2];
    dice[2] = dice[1];
    dice[1] = dice[5];
    dice[5] = tmp;
}
void south()
{
    int tmp = dice[0];
    dice[0] = dice[2];
    dice[2] = dice[4];
    dice[4] = dice[5];
    dice[5] = tmp;
}
void north()
{
    int tmp = dice[5];
    dice[5] = dice[4];
    dice[4] = dice[2];
    dice[2] = dice[0];
    dice[0] = tmp;
}
 
cs


저작자표시

'알고리즘 풀이 > 시뮬레이션' 카테고리의 다른 글

백준 15685 드래곤커브  (0) 2018.09.30
백준 14890 경사로 :: 들짐승  (0) 2018.07.22
백준 3190 뱀 :: 들짐승  (0) 2018.07.22
백준 12100 2048(Easy) :: 들짐승  (0) 2018.07.22

<링크>

https://www.acmicpc.net/problem/3190


<풀이>

-body배열 : body[i][j] = 좌표(i,j)가 내 몸이면 1, 아니면 0

//초기에는 사과의 위치로도 쓰인다. 

-comm배열 : comm[i]=j일 때, j는 i초때 전환하는 방향이다.

-toDir배열 : toDir[i][j] = 꼬리가 좌표(i,j)에 있을 때 이동해야한다면 어느방향으로 가야하는가

0. 머리좌표랑 꼬리좌표 다 (1,1)로 초기화 , body[1][1]=1 체크


1. toDir의 머리좌표에 어느방향으로 떠나는지 기록해놓는다. 나중에 해당좌표에서 꼬리를 옮길 때  머리가 떠난 방향 그대로 옮겨야 하기 때문.


2. 방향 대로 머리를 옮기고 시간을 증가시켜준다.


3. 머리가 간 곳이 벽이거나, body배열을 체크했을 때 해당 좌표가 1이면 상태면 프로그램끝.


4. 머리 좌표에 사과가 없으면 body의 꼬리좌표를 0으로 만들어주고, 꼬리를 옮긴다. 옮길 때 아까 적어두었던 toDir배열 참조해서 그 방향 그대로 옮긴다.


5. body배열의 머리 좌표를 1로 갱신


6. 현재 시간에 방향 전환명령이 있으면 방향 갱신

1~6을 반복하면 된다.


<소스코드>

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<stdio.h>
int toDir[101][101]; //나중에 꼬리가 옮겨야할 방향기록
int body[101][101]; //몸이 어느곳을 차지하고있는지
int toI[4] = { 0,-1,0,1 }; //좌상우하
int toJ[4] = { -1,0,1,0 };
char comm[100000];
int main()
{
    int N, K, L;
    scanf("%d%d", &N, &K);
    int a, b;
    while (K--)
    {
        scanf("%d%d", &a, &b);
        body[a][b] = 2;
    }
    scanf("%d", &L);
    while (L--)
    {
        char c;
        scanf("%d%c%c", &a, &c, &c);
        comm[a] = c;
    }
 
    int sec = 0;
 
    int hi, hj, ti, tj;
    hi = hj = ti = tj = 1;
 
    body[hi][hj] = 1;
 
    int dir = 2;
    while (1)
    {
        ++sec;
        toDir[hi][hj] = dir;
        hi += toI[dir];
        hj += toJ[dir];
        if (hi == 0 || hi == N + 1 || hj == 0 || hj == N + 1 || body[hi][hj] == 1)
            break;
        if (body[hi][hj] != 2) //사과 없으면
        {
            body[ti][tj] = 0;
            int d = toDir[ti][tj];
            ti += toI[d];
            tj += toJ[d];
        }
        body[hi][hj] = 1;
        if (comm[sec] != 0)
        {
            if (comm[sec] == 'L')
            {
                if (dir == 0)
                    dir = 3;
                else
                    dir -= 1;
            }
            else
                dir = (dir + 1) % 4;
        }
 
    }
    printf("%d", sec);
}
cs


저작자표시

'알고리즘 풀이 > 시뮬레이션' 카테고리의 다른 글

백준 15685 드래곤커브  (0) 2018.09.30
백준 14890 경사로 :: 들짐승  (0) 2018.07.22
백준 14499 주사위굴리기 :: 들짐승  (0) 2018.07.22
백준 12100 2048(Easy) :: 들짐승  (0) 2018.07.22

+ Recent posts

티스토리툴바