백준 알고리즘 1193번 문제풀이(JAVA)

이 문제... 보자마자 감 안왔다. 엥 이걸 어떻게 구하지 대체. 근데 분명 방법이 있을텐데 내가 모르는 거고 문제를 딱 읽었을 때 아 이렇게 하면 되겠다 라는 감이 보통 오는데 안왔다. 브론즈1 문제인데도 몰라서 한숨이 나왔다. 하지만 어떻게든 풀어보자 라는 생각으로 로직 생각을 시작했다.

 

 처음 접근 방법을 순서 값에 규칙이 있지 않을까 싶어서 '몇 번째 순서' 여기에 초점을 맞췄다. 행이 0이거나 열이 0인 칸들을 제외하고 나머지들은 오른쪽 대각선 방향으로 4n만큼 증가한다. 즉 2/2는 5번째로, 1/1(1번째)에서 +4이다. 이렇게 접근하니 문제를 해결할 수 없었다. 위->아래 방향 또는 아래 -> 위 방향 이렇게 고정된 것이 아닌 번갈아가면서 대각선 방향이 바뀌기 때문에 규칙을 찾긴 찾아도 값을 얻기 위한 계산이 매우 복잡했다.

 

아무리 생각해도 모르겠어서 구글링 해 보았다. 힌트를 조금 얻었다. n까지의 개수를 이용해 구하는 방식이었다. 그래서 최종적으로는

 n까지의 개수, 짝수/홀수의 대각선 방향, 그에 따른 분모,분자값의 증가/감소를 이용해 해결할 수 있었다.

 

 이 문제에서의 교훈. '문제에서 접근 힌트를 얻자' 이다. 지그재그 방향... 짝수 인덱스에서는 올라가고 홀수 인덱스에서는 내려간다는 것을 알아채면 조금 더 빨리 해결할 수 있지 않았을까 싶다. 처음에 아예 잘못된 방향으로 갔더니 다른 방향을 생각해보지 않았다. 이것도 고쳐야할 점이다. 잘못됐다 싶으면 아예 다른 방식의 로직 생각해보기.

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

public static void main(String[] args) throws IOException {

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

int x = Integer.parseInt(br.readLine());
int line = -1;
int n = 0;
int prev = 0;
int rest = 0;

if(x == 1) {
System.out.println(x + "/" + x);
return;
}

while(true) {
if( x <=(n*(n+1)/2)) {
prev = n*(n-1)/2;
rest = x - prev;
break;
}
line++;
n++;
}

if(line % 2 == 1) {
int mm = line + 1 - (rest - 1);
int nn = 1 + (rest - 1);
System.out.println(nn + "/" + mm);
}else {
int mm = 1 + (rest - 1);
int nn = line + 1 - (rest - 1);
System.out.println(nn + "/" + mm);
}
}
}

---