[백준 알고리즘] 1993번: 분수찾기
December 19, 2019
1993번: 분수찾기
나열된 분수들을 1/1 -> 1/2 -> 2/1 -> 3/1 -> 2/2 -> … 과 같은 지그재그 순서로 차례대로 1번, 2번, 3번, 4번, 5번, … 분수라고 하자.
X가 주어졌을 때, X번째 분수를 구하는 프로그램을 작성하시오.접근 방법:
규칙을 찾아보려고 했는데 보니까 지그재그니까 홀수 행에서는 위로, 짝수행에서는 아래로 이동한다. 그리고 홀수 행에서는 분모가 1씩 늘어나고 분자가 1씩 줄어든다. 짝수 행에서는 분모가 1씩 줄어들고 분자가 1씩 늘어난다. 이 규칙을 수식화 하면 풀 수 있을 것 같다. 그리고 한번 이동할 때마다 열만큼 이동하면 된다. 주어진 숫자에 다다를때까지 이 규칙대로 계속 진행하면 결과를 바로 알 수 있을 것 같다.
- 해결 후 : 해결하고 다른 사람이 짠 숏코딩을 봤는데 진짜 대단하다.. 접근 방법이 비슷해도 그걸 구현해내는 능력이 참 다른 것 같다. 15줄만에 끝내는 어떤 코드를 보면서 존경스러운 생각이 들었다..
통과 코드:
#include <iostream>
using namespace std;
int main(){
int N, den = 1, num = 1; // 분모, 분자 1, 1로 초기화
int j = 0, i = 1, sum = 0;
cin >> N;
while(1){
for (j = 0 ; j < i ; j++){
if (sum + j+1 == N){ // 총 계산 횟수가 N만큼 되면 종료. j+1을 해주는건 j가 0부터 시작하기 때문에 하나 올려줘야 제대로 카운트 된다.
cout << num << "/" << den << endl; // 결과 출력하고 끝내기
return 0;
}
if (i%2!=0){ // 홀수 열에서는 분모+1 분자-1
den+=1;
num-=1;
}
else{ // 짝수 열에서는 분모-1, 분자+1
den-=1;
num+=1;
}
if (den<1) den = 1; // 맨끝에 도달하면 안빼고 그대로 유지하니까 0이되면 다시 1로 돌려놓자
if (num<1) num = 1;
}
sum += j; // 현재까지 연산갯수를 누적하고
i++; // 다음 열로 이동
}
return 0;
}
