분수 찾기 알고리즘 아이디어

https://www.acmicpc.net/problem/1193

1193번: 분수찾기

위 문제를 며칠이 지나도록 풀지 못했었다.

먼저 필자는 위 문제를

분자: 11232211234543211234567654321

분모:121123432112345654321123456787654321

와 같은 수열로 접근했지만 이를 구현할 방법을 알지 못했다.

 

핵심은 필자가 접근한 방식보다 구현이 훨씬 쉬운

대각선 라인이라는 아이디어가 있었다.

while(x>i){
		x-=i;
		i++;
	}

여기서 x는 주어진 x이고, i(초기화 i = 1)는 대각선 라인번호이다.

각 라인에는 각 라인번호만큼의 분수가 존재한다.

따라서 x가 1번 라인에 속한 분수의 갯수보다 크다면 1을 빼준다.

또 x가 2번 라인에 속한 분수의 갯수보다 크다면 2를 빼준다.

이 반복문이 끝나고 나면 i에는 대각선의 라인번호, x에는 그 라인 번호에서 몇 번째 분수인지에 대해 알 수 있다.

 

이 아이디어에서 배웠던 점은 반복문 조건의 양변을 변화시킨 것이다.