문제
준규가 사는 나라는 우리가 사용하는 연도와 다른 방식을 이용한다. 준규가 사는 나라에서는 수 3개를 이용해서 연도를 나타낸다. 각각의 수는 지구, 태양, 그리고 달을 나타낸다.
지구를 나타내는 수를 E, 태양을 나타내는 수를 S, 달을 나타내는 수를 M이라고 했을 때, 이 세 수는 서로 다른 범위를 가진다. (1 ≤ E ≤ 15, 1 ≤ S ≤ 28, 1 ≤ M ≤ 19)
우리가 알고있는 1년은 준규가 살고있는 나라에서는 1 1 1로 나타낼 수 있다. 1년이 지날 때마다, 세 수는 모두 1씩 증가한다. 만약, 어떤 수가 범위를 넘어가는 경우에는 1이 된다.
예를 들어, 15년은 15 15 15로 나타낼 수 있다. 하지만, 1년이 지나서 16년이 되면 16 16 16이 아니라 1 16 16이 된다. 이유는 1 ≤ E ≤ 15 라서 범위를 넘어가기 때문이다.
E, S, M이 주어졌고, 1년이 준규가 사는 나라에서 1 1 1일때, 준규가 사는 나라에서 E S M이 우리가 알고 있는 연도로 몇 년인지 구하는 프로그램을 작성하시오.
입력
첫째 줄에 세 수 E, S, M이 주어진다. 문제에 나와있는 범위를 지키는 입력만 주어진다.
출력
첫째 줄에 E S M으로 표시되는 가장 빠른 연도를 출력한다. 1 1 1은 항상 1이기 때문에, 정답이 음수가 나오는 경우는 없다.
알고리즘 분류
#include<stdio.h>
#include<stdlib.h>
int main(){
int e,s,m;
int d = 1;
scanf("%d %d %d",&e,&s,&m);
int a=1,b=1,c=1;
while(a!=e || b!=s || c!=m){
a++;
b++;
c++;
if(a == 16) a = 1;
if(b == 29) b = 1;
if(c == 20) c = 1;
d++;
}
printf("%d\n",d);
}
의외로 간단 !?
문제를 보고 답을 보니, 의외로 간단 이라는 생각이 떨어졌다.
브루트 포스 알고리즘은 완전탐색 알고리즘 중에서도 매우 비효율적인 알고리즘 중 하나이지만,
그만큼 직관적이기에 작동 방식과 작성 방법만 알면
브루트 포스 알고리즘
을 이용하는 문제는 쉽게 해결할 수 있다.
애초헤 브루트가 brute 무식한의 의미고
포스가 force 힘이다.
따라서 이 알고리즘은 가능한 모든 경우의 수를 모두 탐색하고,
문제에서 제시하는 요구조건에 충족되는 결과만을 우리에게 도출해준다.
따라서 이론상 예외없이 100%의 확률로 정답을 가져다준다.
문제 해결 방법을 간단히 설명하자면,
1. 주어진 문제를 선행의 구조로 전환해서 생각하라!
2. 구조화된 문제공간을 적잘한 방법으로 해를 구성할 때까지 탐색하라!
3. 구성된 해들을 정리해보라!
최근 잡마켓에서 코딩테스트를 할 때
브루투 포스를 이용한 알고리즘 문제는 거의 출제되지 않는다.
그도 그럴것이 효율적이지 못 한 방식이기 때문이다.
그렇다고해서 중요하지 않은 것은 아니니 원리만은 이해하도록 하자.