백준 1476, 1107 (C++)

1476 : www.acmicpc.net/problem/1476

1476번: 날짜 계산

#include <iostream>
int E, S, M;

int CalculateYear(){
    int result = 1;

    while(true){
        if((result - E)%15 == 0 && (result - S)%28 == 0 && (result - M)%19 == 0)
            return result;
        result++;
    }
}

int main() {
    scanf("%d %d %d", &E, &S, &M);

    printf("%d", CalculateYear());
}

- 결과 result는 15, 28, 19의 배수로 나오게 됨

- 현재 E, S, M은 각각 15, 18, 19를 나눈뒤 남은 나머지를 뜻함.

    - 이를 이용해서 while, break를 사용해서 날짜를 구함

 

- 1부터 올라가는 연산인데 생각보다 엄청 빨리 된다

 

---

1107 : www.acmicpc.net/problem/1107

1107번: 리모컨

#include <iostream>
#include <cmath>
using namespace std;
bool broken[10];

int Possible(int n){
    // count는 만약 채널을 갈 수 있다면 가능한 채널로 가는데 눌러야 하는 버튼의 수를 저장해줌
    int count = 0;
    if(n == 0) {
        if(!broken[0]) 
            return 1;
        else
            return 0;
    }
    while(n){
        if(broken[n % 10])
            return 0;
        n /= 10;
        count++;
    }
    return count;
}

int main(){
    int N, M;
    scanf("%d", &N);
    scanf("%d", &M);

    for(int i = 0; i < M; i++){
        int j;
        scanf("%d", &j);
        broken[j] = true;
    }

    int a = abs(100-N);
    for(int i = 0; i <= 1000000; i++){
        int count = Possible(i);
        if(count > 0){
            int b = abs(N-i);
            if(a > b + count)
                a = b + count;
        }
    }

    printf("%d", a);
    return 0;
}

- 정신나간 문제 / 관점만 다르게 하면 바로 풀리는 문제

- 부르트포스 알고리즘이라고 하고 쉬운말로 때려박기라고 한다

- 중요한 포인트

    - 입력가능한 채널은 500,000 이상이다, 즉 500,001를 입력한 뒤 내려가도 된다는 뜻

    - 컴퓨터 속도는 생각보다 빠르다. 클럭수 믿고 그냥 완전탐색하면 금방 나온다

 

- Possible의 역할

    - main의 for문에서 들어온 i (0~1,000,000 채널 모두 탐색) 가 바로 갈 수 있는 채널인지 나누기를 통해 알아냄

    - 가능하다면 count를 통해 버튼을 총 몇번 눌러야 그 채널로 가는지 알려줌

 

- 코드 요약

    1. 입력을 전부 받음

    2. 일단 abs를 통해 +, -로 가는 값을 구함

    3. 이후 0 ~ 1,000,000값을 하나하나 Possible함수에 넣어서 바로 갈 수 있는 채널인지 알아냄

        - 만약 바로 갈 수 있다면 count를 통해 몇번 클릭하는지 알아냄

    4. Possible로 넣어보니 채널 i는 '바로 갈 수 있는 채널이다!' 라면 i와 원하는 채널 N의 차이 (+, - 로 가는 횟수)를 구함

    5. 이 차이가 b(그냥 +, -로 가는 값)보다 작다면 a에 대입.

    6. for문이 다 돌면 a를 출력

    * 한마디로 가능한 채널을 모두 찾는 것이다