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
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
using namespace std;
 
int mapW, mapH, placeX, placeY, cnt;
int map[27][27] = { 0, };
int moveM[1004] = { 0, };
int dice[6] = { 0,0,0,0,0,0 };
int temp = 0;
bool isin(int a,int b) {
    if (a >= 0 && a < mapW&&b >= 0 && b < mapH)return true;
    else return false;
}
int roll(int a) {
    switch (a) {
    case 1:
        //cout << " 오른쪽"<<endl;
        temp = dice[1];
        dice[1] = dice[2];
        dice[2] = dice[3];
        dice[3] = dice[5];
        dice[5] = temp;
        cout << dice[5] << endl;
        break;
    case 2:
        //cout << "왼쪽" << endl;
 
        temp = dice[3];
        dice[3] = dice[2];
        dice[2] = dice[1];
        dice[1] = dice[5];
        dice[5] = temp;
 
        cout << dice[5] << endl;
        break;
    case 3:
        //cout << "위로"<<endl;
        temp = dice[0];
        dice[0] = dice[2];
        dice[2] = dice[4];
        dice[4] = dice[5];
        dice[5] = temp;
        cout << dice[5] << endl;
        break;
    case 4:
        //cout << "아래로"<<endl;
        temp = dice[5];
        dice[5] = dice[4];
        dice[4] = dice[2];
        dice[2] = dice[0];
        dice[0] = temp;
        cout << dice[5] << endl;
        break;
    }
    return 0;
}
void search(int k) {
    for (int i = 0; i < cnt; i++) {
        
        if (moveM[i] == 1 && isin(placeX, placeY+1)) {
            roll(1);
            if (map[placeX][placeY+1] == 0) map[placeX][placeY + 1] = dice[2];
            else {
                dice[2] = map[placeX][placeY + 1];
                map[placeX][placeY + 1] = 0;
            }
            //cout << "굴린다음에 아래에있는 숫자를 map[" << placeX << "][" << placeY << "]로 바꿈"<<endl;
            placeY++;
        }
        if (moveM[i] == 2 && isin(placeX, placeY-1)) {
            roll(2);
            if (map[placeX][placeY-1] == 0) map[placeX][placeY-1] = dice[2];
            else{ dice[2] = map[placeX][placeY-1];
            map[placeX][placeY - 1] = 0;
            }
            //cout << "굴린다음에 아래에있는 숫자를 map[" << placeX << "][" << placeY << "]로 바꿈"<<endl;
            placeY--;
        }
        if (moveM[i] == 3 && isin(placeX-1, placeY)) {
            roll(3);
            if (map[placeX-1][placeY] == 0) map[placeX-1][placeY] = dice[2];
            else{ dice[2] = map[placeX-1 ][placeY];
            map[placeX-1][placeY] = 0;
            }
            //cout << "굴린다음에 아래에있는 숫자를 map[" << placeX << "][" << placeY << "]로 바꿈"<<endl;
            placeX--;
        }
        if (moveM[i] == 4 && isin(placeX+1, placeY)) {
            roll(4);
            if (map[placeX+1][placeY] == 0) map[placeX+1][placeY] = dice[2];
            else {dice[2] = map[placeX+1][placeY];
            map[placeX+1][placeY ] = 0;
            }
            //cout << "굴린다음에 아래에있는 숫자를 map[" << placeX << "][" << placeY << "]로 바꿈"<<endl;
            placeX++;
        }
        //cout << "현재아랫면" << dice[2] << endl;
    }
}
int main() {
    //freopen("test.txt", "r", stdin);
    cin >> mapW >> mapH >> placeX >> placeY >> cnt;
    for (int i = 0; i < mapW; i++) {
        for (int j = 0; j < mapH; j++) {
            cin >> map[i][j];
 
        }
    }
    for (int i = 0; i < cnt; i++) {
        cin >> moveM[i];
    }
 
    search(0);
}
cs


원시적인코드 dice[] 배열에 현재 좌우앞뒤위아래 상황을 다 저장한다

'재미있는공부이야기 > 알고리듬' 카테고리의 다른 글

백준 17071번 숨바꼭질 5  (0) 2019.03.21
백준 9019번 DSLR  (0) 2019.02.28
백준 7569번 토마토  (0) 2019.02.20
백준 2178번 미로찾기  (0) 2019.02.20
KMP 알고리즘  (0) 2019.02.15

모든 경우의수  다해보는거


ex) 비번 4자리면

0000 부터 9999까지

총 1만가지


시도해보는 경우의수가 중요


비번이 12자리이고 

경우의수가 0이 12개있는거부터 9가 12개있는거까지 1조 가지 경우의수


1.문제의 가능한 경우의 수를 계산해본다 -> 손으로

2. 가능한 모든방법을 다 만들어본다. -> 빠짐없이해야됨. 그냥해보기, for문, 순열, 재귀, 비트마스크

3. 각각의 방법을 이용해서 답을 구해본다. 


시간복잡도 O(경우의수 x 방법1개를 시도해보는데 걸리는시간복잡도)


걍 다해보기 -) 2309 일곱난쟁이 

1476 날짜계산 ( 중국인의 나머지정리? 도 있긴한데 안중요)

14500 테트로미노


'재미있는공부이야기 > 혼자끄적' 카테고리의 다른 글

N중포문 순열사용하기  (0) 2019.02.28
수학  (0) 2019.02.26


수학


1. 나머지연산 

정답을 구할때 너무크면 나머지로 출력하는문제많음.

최종에서하지말고

매번나머지해도됨


나머지연산은 덧셈곱셈에 닫혀있고, 뺄셈도있긴한데 다름

나누기연산은 안됨 (6/3)%3 이 그 예

10403문제

빼기예제 (6-5)%3 = 1

파이썬에서는 1나오는데

C++ 이나 java는 -2가 나옴

그래서 각자나머지한거에서 나누는수 한번 더 해주면 성립


페르마의소정리

(a/b) %c

 = (a x b^(c-2) ) % c

 (단 c는 소수, a 와 b는 서로소)



2. 최대공약수


정답이 분수형태일때 기약분수 나타낼때

GCD


int g = 1;

for(int i = 2; i<=min(a,b) ; i++){

if(a%i == 0 && b % i ==0 ) {

g = i ;

}

}

시간복잡도 O(N)

유클리드 호제법이 더좋음

 GCD(a,b) = GCD(b,a%b)

재귀쓸때

int gcd(int a, int b){

if(b==0){

return a;

 } else{

return gcd(b,a%b);

}

}

유클리드호제법 시간복잡도 O(log N)

 안쓸대

int gcd(int a, int b) {

while(b!=0){

int r = a%b;

a =b;

b =r;

}

return a;

}

이것도 시간복잡도 O(log N)


GCD(a,b,c)  = GCD(GCD(a,b),c)


최소공배수



3. 소수


약수가 1이랑 자기자신

1) 어떤수가 소수이닌지 판별

2보다크고 N보다작은것들로 나눠

2보다크고 N/2보다 작은것들로 나눠

2보다크고 루트N보다 작은것들로 나눠 O(루트N)


2) N보다 작거나 같은 소수 찾아내기( N까지수를 루트N으로 조지니까 O(N루트N)


에라토스테네스의 체

2~100까지는 2 3 5 7 로 인해서 다지워짐  


int prime[100];

int pn = 0;

bool check[101] ;

int n = 100;

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

if(check[i] == false){

prime[pn++]=i;

for(int jk =i*i; j<=n; j+=i){

check[j] = true;

}

}

}

이미검사한 영역에대해서 당겨서 검사하는거 중요

시간복잡도 O(Nlog(logN))


골드바흐의 추측

2보다 큰 모든 짝수는 두 소수의 합으로 표현 가능하다.

위문장에 3을 더하면

5보다 큰 모든 홀수는 세소수의 합으로 표현 가능하다


진짜 추측임 10의 18승 이하에서는 참인것이 증명됨

결국 에라토스 체에서 false로 그 배열 자리에 소수인놈 저장해놨으니

수가 크면 한쪽소수 정해놓고 p+q = N 이런식으로해서 p 정해보고

 N-p가 false인지 체크해보면됨

'재미있는공부이야기 > 혼자끄적' 카테고리의 다른 글

N중포문 순열사용하기  (0) 2019.02.28
브루트포스  (0) 2019.02.26

+ Recent posts

티스토리툴바