백준 1476, 1107 (C++)
1476 : www.acmicpc.net/problem/1476
1476번: 날짜 계산
준규가 사는 나라는 우리가 사용하는 연도와 다른 방식을 이용한다. 준규가 사는 나라에서는 수 3개를 이용해서 연도를 나타낸다. 각각의 수는 지구, 태양, 그리고 달을 나타낸다. 지구를 나타
www.acmicpc.net
#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번: 리모컨
첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼
www.acmicpc.net
#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를 출력
* 한마디로 가능한 채널을 모두 찾는 것이다