[JAVA-D3] SWEA 1493 - 수의 새로운 연산

SW Expert Academy

 

🤔 문제 풀이

느낌상 별다른 알고리즘이 필요한 문제는 아니고 빡구현 문제였던거 같다.

1사분면내에서 대각선으로 수가 커지기 때문에 규칙성을 잘 파악해야했다.

 

대각선으로 증가하는 수들을 어떻게 저장할까 고민하다가, 시간이 오래 걸릴 것을 우려하여

수 전체를 저장하지 않고 x=1인 라인의 y값들을 ylist에 저장해놓기로 했다. 

 

 

보면 알겠지만 x=1 라인의 경우 초기(value) 1, 증가 값 (addict) 0 이라고 할 때

value = value + (addict++) 이라는 규칙을 발견할 수 있다. (1+0, 1+1, 2+2, 4+3 ...)

 

주어지는 p와 q의 y좌표를 구하기 위해 ylist를 순회하며 ylist.get(i) > p or q 인 경우

i - 1 이 y좌표가 되며, ylist.get(i) = p or q 라면 i 가 y좌표가 되게끔 했다.

 

구한 p와 q의 x,y좌표를 서로 더하는 연산을 수행하고 결과로 얻은 새로운 ax, ay좌표의 값을 구해야했다.

ylist 의 값으로부터 오른쪽으로 이동할 때 각각의 수들은

x=1일때 y=n의 값 ylist.get(ay) 에서 + ay + addict++)의 규칙성을 갖는다.

ax에 도달할 때 까지 오른쪽으로 이동하면 답을 구할 수 있다. 하지만 나는 런타임 에러가 났다.

 

✅ 문제점

기본적으로 주어지는 예제 테스트케이스는 맞았으나 제출을 했을 때 런타임에러가 났었는데

이는 p와 q의 최대값이 각각 1만까지 이고, p와 q가 1만일 때 ★연산을 수행할 경우

#(20000), 다시말해 2만의 값을 갖는 좌표를 알아야했는데 내가 x=1일때의 구한 y값들인

ylist를 구할 때 그 값이 1만을 넘기 전까지 구하도록 했기 때문에

p와 q가 최대값인 테스트 케이스를 통과하지 못한 것이다.

 

값이 1만을 넘지 않을 때까지 ylist를 구했을 때의 그 size가 141이기 때문에

#(20000)을 고려하여 ylist를 구할 때 ylist.size() <= 282 일때까지로 while반복문의 조건을 수정했다.

 

만약 IDE를 쓸 수 있는 코딩테스트였다면 IDE 디버깅을 통해어디가 틀렸는지를 알 수 있었겠지만,

대부분이 IDE를 사용하지 못하기 때문에 실전이었다면 히든 테케를 생각하지 못하고

틀렸을 것이라고 생각한다,,, 문제의 조건을 좀 더 자세히 읽고 그에 따른 히든 테케를 잘 생각할 수 있도록 해야겠다.

 

import java.io.*;
import java.util.*;

class Solution {
	static ArrayList<Integer> ylist;
	public static void main(String args[]) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int T = Integer.parseInt(br.readLine());

		for (int test_case = 1; test_case <= T; test_case++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int p = Integer.parseInt(st.nextToken());
			int q = Integer.parseInt(st.nextToken());
			
			ylist = new ArrayList<>();
			
			int addict = 1;
			int value = 1;
			
			// y좌표를 1부터 시작하기 위함
			ylist.add(0);
			// x=1로 고정, y좌표값들이 저장됨
			while(ylist.size() <= 282) {
				ylist.add(value);
				value += addict++;
			}
			
			int ppoint = 0;
			int qpoint = 0;
			// p 와 q는 (1,i), (i,1) 사이에 있다는 것을 알 수 있음
			for(int i = 1; i<=ylist.size(); i++) {
				if(ylist.get(i) > p) {
					ppoint = i-1;
					break;
				}else if(ylist.get(i) == p){
					ppoint = i;
					break;
				}
			}
			for(int i = 1; i<=ylist.size(); i++) {
				if(ylist.get(i) > q) {
					qpoint = i-1;
					break;
				}else if(ylist.get(i) == q) {
					qpoint = i;
					break;
				}
			}
			
			// p,q값과 ylist 값의 차이(sub)만큼 x에 더해주고 y에 빼주면
			// p,q값을 가지는 좌표를 구할 수 있음
			int sub = p - ylist.get(ppoint);
			int px = 1+sub; int py = ppoint - sub;
			sub = q - ylist.get(qpoint);
			int qx = 1+sub; int qy = qpoint - sub;
			
			int ax = px+qx; int ay = py+qy;
			
			// (ax,ay) 좌표의 값을 구해야함
			// (1,ay)=ylist.get(ay) 에서 좌측으로 ax까지 움직여야함
			// 이때 좌측으로 1칸움직일때마다 값은 (1,ay) + (ay+(addict++)) 이 된다. 
			int answer = ylist.get(ay);
			addict = 1;

			for(int i = 1; i<ax; i++) {
				answer = answer + ay + (addict++);
			}
			
			bw.write(String.format("#%d %d\n", test_case, answer));
		} // end of testcase
		bw.flush();
	}
}