1. 문제 상세
https://www.acmicpc.net/problem/1193
2. 문제 접근
대각선을 따라 지그재그 순서로 분수를 확인하여 해당 순서의 분수를 출력하는 것이 문제이다.
이를 참고해서, 대각선을 보고 규칙을 찾아보자.
대각선의 분수들을 보면 i 번째 대각선인 경우 그 대각선에는 i 개의 분수가 있다.
이에 따라 먼저 내가 입력받은 순서가 몇 번째 대각선에 있는지를 확인하자.
이를 확인하기 위해 입력받은 순서 n 에서 i 를 1씩 증가시키며 빼준다.
n 이 i 보다 작거나 같아졌다면 i 번째 대각선에 내가 입력받은 순서가 있다는 것이다.
그리고 지그재그 순서이므로 대각선에서 분수들의 순서에도 규칙이 있다.
짝수 i 번 대각선이라고 할 때, 그 대각선 안의 분수는 1/i, 2/i - 1, 3/i - 2, ... i/1 순서이다.
홀수 i 번 대각선인 경우, 대각선 안의 분수는 i/1, i - 1/2, i - 2/3, ... 1/i 순서가 된다.
즉 짝수 i 번 대각선에서는 분자가 1부터 i 까지 증가, 홀수 i 번 대각선에서는 분모가 1부터 i 까지 증가 한다는 것이다.
따라서 위에서 n 을 통해 구한 i(대각선 번호)가 홀수인지 짝수인지에 따라 i 보다 작아진 n 이 분모나 분자가 될 것이고,
i 에 1을 더한 값에서 i 보다 작아진 n 을 빼서 나머지 분모나 분자를 구할 수 있다.
정리해보면 대각선 i 는 1부터, 입력받은 순서가 n 일때, n 에서 i 를 1씩 증가시키며 빼주고, n 이 i 보다 작거나 같아졌을 때
i 번째 대각선이 짝수번이면 분자가 n, 분모는 그 반대인 (i + 1) - n 값이다.
i 번째 대각선이 홀수번이면 분모가 n, 분자가 그 반대인 (i + 1) - n 값이다.
3. 문제 풀이
#include <iostream>
using namespace std;
int main() {
int n, i = 1;
cin >> n;
while(n > i) {
n -= i;
i++;
}
if(i % 2 == 0) cout << n << "/" << (i + 1) - n << endl;
else cout << (i + 1) - n << "/" << n << endl;
}
정수 n 과 i 를 선언하고 i 를 1로 초기화한다.
cin 으로 정수(순서)를 입력받아 n 에 저장한다.
while문으로 n 이 i 보다 큰 경우 반복하도록 한다.
n 의 값에서 i 를 빼고, i 에 1을 더해준다.
반복이 끝나면 if 문으로 i 를 2로 나눈 나머지가 0인 경우(즉, 짝수인 경우) n 의 값과 / 문자, (i + 1) - n 값을 출력한다.
위의 경우가 아닐 때(홀수인 경우) (i + 1) - n 값과 / 문자, n 의 값을 출력한다.
4. 성능 확인
5. 마무리
알맞은 규칙을 얼마나 빠르게 찾는지가 문제해결의 관건인 것 같다.
'백준 - 단계별로 풀어보기 > 일반 수학 1' 카테고리의 다른 글
[백준] 2869번 : 달팽이는 올라가고 싶다 | C++ (0) | 2023.10.18 |
---|---|
[백준] 2292번 : 벌집 | C++ (0) | 2023.10.18 |
[백준] 2903번 : 중앙 이동 알고리즘 | C++ (0) | 2023.10.18 |
[백준] 2720번 : 세탁소 사장 동혁 | C++ (0) | 2023.10.18 |
[백준] 11005번 : 진법 변환 2 | C++ (0) | 2023.10.13 |