[SWEA / Java] 1493번: 수의 새로운 연산 (D3)

문제 풀이 날짜: 2023.07.25
포스트 작성일: 2023.07.25

 

* 학습 목적으로 작성하는 글입니다. 풀이가 정석적이지 못할 수도 있습니다.

 

문제 출처

Software Expert Academy 1493번: 수의 새로운 연산 (D3)

 

키워드

배열 다루기, 구현

 

풀이 접근법

• 수의 증가 규칙을 찾아 처음부터 배열을 초기화 하였다. 육안으로 보기에는 파란색 화살표를 따라 대각선 아래 방향으로 증가 규칙이 있는 듯하나, 가로줄과 세로줄의 증가 규칙을 따로 찾는 것이 구현하기 쉬웠다.
• 세로줄은 아래에서 위로 1, 2, 3, 4, 5, ... 씩 증가한다.
• 첫 번째 가로줄은 왼쪽에서 오른쪽으로 2, 3, 4, ... 씩 증가
  • 두 번째 가로줄은 왼쪽에서 오른쪽으로 3, 4, 5, ... 씩 증가
  • 세 번째 가로줄은 왼쪽에서 오른쪽으로 4, 5, 6, ... 씩 증가
  • → 가로줄 윗쪽으로 갈 수록(i값이 커질 수록) 시작점이 1씩 늘어난다.
• 이 규칙대로 배열을 초기화 하면서 Map<Integer, Point>에 <배열값, 위치> 쌍을 저장한다.
  • 배열이 커질 수록 반복문으로 원하는 값을 찾는데 오래 걸린다.
  • Map을 이용하면 입력으로 온 p, q의 위치값을 빠르게 찾을 수 있다. 

 

코드

import java.util.*;
import java.io.*;
import java.awt.Point;

class Solution
{
	private static final int MAX_SIZE = 300;
	
	private static Map<Integer, Point> map = new HashMap<>();
	private static int[][] matrix = new int[MAX_SIZE + 1][MAX_SIZE + 1]; //0은 사용 안 함
    
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());

		//1.규칙에 맞게 matrix를 생성
		initializeMatrix();
		
		StringBuilder sb = new StringBuilder();
		for(int test_case = 1; test_case <= T; test_case++) {
			String[] temp = br.readLine().split(" ");
			
			int p = Integer.parseInt(temp[0]);
			int q = Integer.parseInt(temp[1]);
			
			//2.주어진 연산 수행
			Point p1 = map.get(p);
			Point p2 = map.get(q);
			
			int nx = p1.x + p2.x;
			int ny = p1.y + p2.y;
			
			int answer = matrix[ny][nx];
			
			sb.append("#").append(test_case).append(" ").append(answer).append("\n");
		}
		System.out.println(sb);
	}

	private static void initializeMatrix() {
		//세로줄 초기화
		int k = 1;
		matrix[1][1] = 1;
		map.put(matrix[1][1], new Point(1, 1));
		
		for(int i = 2; i <= MAX_SIZE; i++) {
			matrix[i][1] = matrix[i - 1][1] + (k++);
			map.put(matrix[i][1], new Point(1, i)); //row & col 순서 주의
		}
		
		//가로줄 초기화
		k = 2;
		for(int i = 1; i <= MAX_SIZE; i++) {
			for(int j = 2; j <= MAX_SIZE; j++) {
				matrix[i][j] = matrix[i][j - 1] + (k + j - 2);
				map.put(matrix[i][j], new Point(j, i)); //row & col 순서 주의
			}
			k++;
		}
	}
    
}

---

Map으로 탐색 시간을 단축하는 것도 중요하지만, 배열의 증가 규칙을 찾는 것이 특히나 어려운 문제였다. 아직 시뮬레이션 문제나 규칙 찾기 문제에 약하기 때문에 이러한 문제를 더욱 많이 푸는 것이 좋겠다.

 

참고한 블로그

https://velog.io/@gkdud583/JAVA-SWEA-1493-수의-새로운-연산

 

git 링크

(git 링크 첨부)