SWEA 1493 수의 새로운 연산

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

체감상 난이도는 D4였다ㅠㅠ 수에 약해서 진짜 너무 힘들었음..

대각선으로 수가 1씩 늘어나는 규칙을 찾고 그 규칙을 방정식으로 구현할 수 있으면 할만하다.

두 가지 방식으로 풀 수 있는데 

1. 미리 배열을 만들고 각 배열에 어떤 값이 들어가는지 계산하고 문제 시작
2. 테스트케이스마다 값이 들어오면 즉시 좌표로 계산하고, 다시 좌표를 값으로 변환

배열을 200 x 200 하니까 부족하고 300x300으로 하면 괜찮았다.

보면 y가 1씩 늘어날때마다 차가 1씩 늘어나는 계차수열이다.

그럼 다음과 같은 공식을 도출할 수 있다.

y가 n일 때, y 레벨에서 가질 수 있는 값의 범위:

$$ 1 + {n \times (n-1) \over 2}  \le y의 범위 \le 1 + {n \times (n-1) \over 2} + (n-1) $$

 

방법1

 initArr()에서 미리 arr를 구해준다. 시간 효율이 훨씬 좋아진다.

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

/**
 * 수의 새로운 연산
 * 그래프 대각선 줄 계차수열로 연산하는거 
 * */

public class Solution{
	static int N = 300;
	static int[][] arr = new int[N+1][N+1]; 
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		initArr();
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(in.readLine());
		int p, q, x=0, y=0, z=0, w=0, result = 0;
		
		for(int tc=1; tc<=T; tc++) {
			StringTokenizer st = new StringTokenizer(in.readLine(), " ");
			p = Integer.parseInt(st.nextToken());
			q = Integer.parseInt(st.nextToken());
			
			for(int r=1; r<=N; r++) {
				for(int c=1; c<=N; c++) {
					if(arr[r][c] == p) {
						x = r;
						y = c;
					}
					if(arr[r][c] == q) {
						z = r;
						w = c;
					}
				}
			}
			result = arr[x+z][y+w];
			System.out.printf("#%d %d\n",tc,result);
		}

	}
	
	private static void initArr() {
		int num = 1;
		for(int r=1; r<=N; r++) {
			arr[r][1] = num;
			for(int c=2; c<=N; c++) {
				arr[r][c] = arr[r][c-1] + r + c - 1;
			}
			num += r;
		}
		
		
	}

}

 

 

방법2

y를 레벨로 잡고 입력된 value가 y 레벨 최대값보다 작으면 그 레벨에서 y,x 좌표를 찾아주는 방식이다. 0레벨부터 시작했기 때문에 level * (level -1) / 2 + 1로 풀어줬다.

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

/**
 * 수의 새로운 연산
 * 그래프 대각선 줄 계차수열로 연산하는거 
 * */

public class Solution{
	
	public static class Pos{
		int x;
		int y;
		
		Pos(int y, int x){
			this.y = y;
			this.x = x;
		}
	}
	
	private static Pos valueToPos(int value) {
		int level = 0;
		int gap = 0;
		for(; level <= 300; level++) {
			if(value <= 1 + level * (level + 1) / 2 + level) {
				gap = value - (1 + level * (level + 1) / 2);
				break;
			}
		}
		return new Pos(level - gap + 1, 1 + gap);
	}
	
	private static int posToValue(Pos p) {
		int level = p.y + p.x - 1;
		return level * (level-1) / 2 + p.x;
	}
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(in.readLine());
		for(int tc=1; tc<=T; tc++) {
			String[] pq = in.readLine().trim().split(" ");
			Pos p1 = valueToPos(Integer.parseInt(pq[0]));
			Pos p2 = valueToPos(Integer.parseInt(pq[1]));
			
			int result = posToValue(new Pos(p1.y + p2.y, p1.x + p2.x));
			System.out.printf("#%d %d\n",tc,result);
		}
	}
}