[백준 C++] 1193 분수찾기
문제
무한히 큰 배열에 다음과 같이 분수들이 적혀있다.
이와 같이 나열된 분수들을 1/1 → 1/2 → 2/1 → 3/1 → 2/2 → … 과 같은 지그재그 순서로 차례대로 1번, 2번, 3번, 4번, 5번, … 분수라고 하자.
X가 주어졌을 때, X번째 분수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 X(1 ≤ X ≤ 10,000,000)가 주어진다.
출력
첫째 줄에 분수를 출력한다.
https://www.acmicpc.net/problem/1193
풀이
개인적으로 브론즈문제치고 처음보면 어떻게 접근할지 고민할만한 문제다.
웬만한 좌표계에서 이동하는 점에대한 위치를 구할때 항상
방향벡터인 dx dy를 선언하는것을 추천한다. 이것만 구현하면 문제는 쉽다.
위그림대로 문제에서 지그재그로 이동하는것은 1-2-3-4-1-2-''' 순으로 움직이고, 각각의 경우의 방향벡터는 아래그림처럼 표현가능하다.
dir는 dx, dy에 쓰일 방향순서이다.. 우측(3) 하측(1) 으로이동시에는 총 1번만 이동하고 다시 방향을 틀어야하므로, bool check변수를 사용했다.
브론즈문제치고 상당히 값진 문제라고 생각된다.
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
int X;
int dx[4] = {1, 1, -1, 0}; //좌하, 하, 우상, 우 순서로반복
int dy[4] = {-1, 0, 1, 1};
int main() {
scanf("%d", &X);
if (X == 1) { //예외처리해버렷음
printf("1/1");
return 0;
}
int dir = 0;
int x = 1, y = 2; //초기값 1/2
bool check = false;
for (int i = 2; i < X; i++) {
int xx = x + dx[dir];
int yy = y + dy[dir];
if (dir == 1 || dir == 3) check = true;
x = xx; y = yy; //분수 갱신
//방향을 바꾸는경우를 체크
if ((dir == 0 && yy == 1) || (dir == 1 && check) ||
(dir == 2 && xx == 1) || (dir == 3 && check)) {
check = false;
dir++;
}
if (dir == 4) dir = 0; //방향 순환
//printf(">> %d %d\n", x, y);
}
printf("%d/%d", x, y);
return 0;
}
Author And Source
이 문제에 관하여([백준 C++] 1193 분수찾기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@cldhfleks2/1193저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)