문제
1193번: 분수찾기
첫째 줄에 X(1 ≤ X ≤ 10,000,000)가 주어진다.
www.acmicpc.net
설계
내가 '수학 1' 문제집에 있는걸 풀면서 느꼈는데 진짜 수학적 사고방식이 중요하다고 느낀다.
왜냐하면 if랑 for문 우다다다 쓰면 풀긴푸는데 효율이 개똥이라..
그리고 for문 무조건 for(int i = 0; i < n; i++) 이런식으로만 사용하려고 하는 습관좀 없애야겠다.
근데 그게 어렵더라..
아무튼 각설하고. 이번 문제는 좀 어려웠다 ㅠㅠ 다른사람은 쉽다는데..
| 1/1 | 1/2 | 1/3 | 1/4 | 1/5 | 1/6 |
| 2/1 | 2/2 | 2/3 | 2/4 | 2/5 | 2/6 |
| 3/1 | 3/2 | 3/3 | 3/4 | 3/5 | 3/6 |
| 4/1 | 4/2 | 4/3 | 4/4 | 4/5 | 4/6 |
| 5/1 | 5/2 | 5/3 | 5/4 | 5/5 | 5/6 |
| 6/1 | 6/2 | 6/3 | 6/4 | 6/5 | 6/6 |
다음과 같은 테이블이 있다.
처음에 문제를 이해못해서 헤맸다;;
이 문제의 순서는 다음과 같이 간다고 생각하면 된다.
그리고 방향이 바뀌기까지를 한 바퀴, 즉 for문에서 1회라고 가정한다면..
이렇게 묶일 것이다.
같은 색상끼리 한 세트라고 볼 수 있다.
여기서 핵심 규칙 첫 번째가 나온다
이 세트가 현재 세번째 세트, 즉 i = 3 이라고 가정해보자.
i 가 3일 때, 즉 홀수일 때는 i/1, i-1/2, i-2/3 식으로 분자가 줄어들고 분모가 늘어나고.
i 가 4일 때, 즉 짝수일 때는 1/i, 2/i-1, 3/i-2, 4/i-3 식으로 분자가 늘어나고 분모가 줄어든다.
이러한 규칙성을 가지고 있다.
그리고 여기서 하나의 추가적인 규칙을 찾을 수 있는데,
하나의 세트 안에 있는 인자들은 각각 분모 + 분자의 합이 같다.
이게 뭔소리냐면, 핑크색 선을 예로 들면 4/1, 3/2, 3/3, 2/4, 1/4 이것들의 분모 + 분자의 합이 각각 5로 모두 같다는 뜻이다.
또한 이 대각선 안에 있는 한 세트 인자들이 갯수가 n = 분자 + 분모 합 n - 1= n 번째 대각선 인것도 확인할 수 있다.
이게 핵심이었다. 그럼 코드를 어떻게 짜야될까?
먼저 1일때는 예외처리를 해주도록 하자.
int n, sum = 0, cnt = 1, num;
//각각 입력받는 수, 대각선 안에 있는 수의 합, 몇번째 대각선인지, 대각선 안에 몇번째 수인지를 판가름하는 변수다.
cin >> n;
if(n == 1){
cout << 1 << "/" << 1;
return 0;
}그 다음, 몇번째 대각선인지 알 필요가 있다.
//분모 + 분자 합이 n보다 작을경우, 다음 대각선으로 이동한다.
//즉, sum이 n보다 크거다 같다면, cnt(대각선 횟수)가 늘어나서 다음 대각선으로 간다고 생각하자.
for(; sum < n; cnt++){
sum += cnt;
}
cnt--;몇 번째 대각선인지 알았으면, 마지막으로 이 대각선 상에서 몇 번째 인자인지 알아보고, 최종적으로 출력해주도록 하자.
정확히는 1+n번째 인자이다. 첫 항이 1로 시작하기 때문에!
//분자, 분모를 선언해주고
//대각선 상에서 몇 번째 인자인지 알려면 sum 에서 입력한 수 n을 빼주면 된다.
int child, parent;
num = sum - n;
if (cnt % 2 == 1) {
child = 1 + num;
parent = cnt - num;
} else {
child = cnt - num;
parent = 1 + num;
}
cout << child << "/" << parent << '\n';
return 0;코드
#include <iostream>
using namespace std;
int main(void){
int n, sum = 0, cnt = 1, num;
//각각 입력받는 수, 대각선 안에 있는 수의 합, 몇번째 대각선인지, 대각선 안에 몇번째 수인지를 판가름하는 변수다.
cin >> n;
if(n == 1){
cout << 1 << "/" << 1;
return 0;
}
//분모 + 분자 합이 n보다 작을경우, 다음 대각선으로 이동한다.
//즉, sum이 n보다 크거다 같다면, cnt(대각선 횟수)가 늘어나서 다음 대각선으로 간다고 생각하자.
for(; sum < n; cnt++){
sum += cnt;
}
cnt--;
//분자, 분모를 선언해주고
//대각선 상에서 몇 번째 인자인지 알려면 sum 에서 입력한 수 n을 빼주면 된다.
int child, parent;
num = sum - n;
if(cnt % 2 == 1){
child = 1 + num;
parent = cnt - num;
} else {
child = cnt - num;
parent = 1 + num;
}
cout << child << "/" << parent << '\n';
return 0;
}결과
진짜... 개어려웠다... 남이 쓴 코드 봐도 이해가안됐다..
내가 멍청한건가.. ㅠㅠㅠㅠㅠ 공부 많이해야겠다..