ch3-1-완전탐색-그냥다해보기

• 가능한 모든 경우의 수를 만들어보고 탐색

• 가능한 모든 경우의 수를 알아야 함

brute force 라고도 부름

• BFS

• 재귀

• 비트마스크

• 순열

• 백트래킹

기법을 주로 사용하여 풀 수 있음

풀어보기

날짜 계산 - 1476

날짜 계산

• E, S, M 이라는 연도를 사용하는 나라가 있음

  • E: 1~15, S: 1~28, M: 1~19

• 각 연도 값이 주어졌을 때, 현재 사용하는 년도 구하기

• 경우의 수 먼저 구해서 brute force 로 할 수 있는지 알아보기

  • E, S, M 은 15*28*19 = 7980 정도 됨. 0~7980 까지 모든 경우의 수를 따져봐도 부담없음

int x, y, z, a, b, c;
cin>>x>>y>>z;
for(int i = 0; ; i+=1) {
    if(a == x && b == y && c == z) {
        cout<<i<<endl;
        break;
    }
    a += 1;
    b += 1;
    c += 1;

    if(a > 15) a = 1;
    if(b > 28) b = 1;
    if(c > 19) c = 1;
}

리모컨 1107

리모컨

• 버튼이 0~9, +, -가 있음

• 일부 숫자 버튼 망가짐

• 초기 채널은 100

• 이동하려는 채널이 N 일 경우 버튼 누르는 최소 횟수 구하기

• bruteforce 느낌남. 모든 경우의수를 먼저 알아보자

  • 채널의 개수가 0~500,000. 1 억개보단 훨씬 적음

• 이동할 수 있는 방법은 다음과 같다.

• 100 번 채널에서 +/-로 이동하기

  • 목적지까지 +/- 누르기.

• 숫자버튼으로 채널 이동하기

  • 숫자버튼으로 채널 이동 (모든 경우의수를 여기서 따질거다)

  • 목적지까지 +/- 누르기.

2 번에서 숫자버튼으로 이동할 경우, 버튼 고장 여부를 따져야한다.

• 각 자리수별로 검사

int possibleNumBtn(int num) {
    // num이 0일 경우, 아래 while문에서 0은 검사하지 못하기 때문에 예외처리.
    if(num == 0) {
        if(broken[0]) {
            return 0;
        } else {
            return 1;
        }
    }

    int len = 0; // 여기서 직접 버튼 개수만큼 +를 해줘서, 고장나지 않았을 경우 버튼 개수만큼 리턴
    while(num > 0) {
        if(broken[num % 10]) {
            return 0;
        }
        len += 1;
        // 1의자리부터 각 자리수별로 검사하기 위해 10으로 나눠준다.
        num /= 10;
    }
    return len;
}

for(int i = 0; i < 1000000; i+=1) {
    int len = possibleNumBtn(i);
    if(len > 0) {
        int oneBtn = target - i;
        if(oneBtn < 0) {
            oneBtn = -oneBtn;
        }

        if(ans > oneBtn + len) {
            ans = oneBtn + len;
        }
    }
}

• 이동하려는 목적지 N 은 0~500,000 까지지만, 채널은 무한대 만큼이다.

  • 그래서, 500000 을 이동할 경우

  • 4,9 가 고장 날 경우

  • 1~500000 까지 이동할 수 있다고 했을 때, 48X,XXX 에서 이동하는게 최소횟수임.

  • 하지만 500000 이상일 경우 500001 에서 -1 로 이동하는게 이득.

• for 문이 백만인 이유는 50 만이 최대 목적지라고 할 때, 0~50 만~100 만 각 50 만 차이로 경우의 수를 구하면 모두 커버 가능하기 떄문이다.

Summary

브루트 포스 문제같을 때는 경우의수를 따져서, 1억 이하인 경우 모든 경우의수를 구한다

• 모든 경우의 수 중

  • 최소값

  • 최대값

  • 해답

    등 을 찾는다.