[SW Expert Academy Java] 4112 이상한 피라미드 탐험

문제

---

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWJHmLraeEwDFAUH 

SW Expert Academy

풀이방법

---

처음에는 모든 숫자에게 높이를 부여하는 배열을 생성해서 bfs를 돌릴려 그랬다.

하지만 피라미드를 그려서 최적경로를 찾아보니 굳이 그럴 필요가 없다는 것을 알았다.

 

while(num<a) {
				num=num+ah;
				ah++; //a의 높이 구하기
			}
			
			ah=ah-1;
			aw=a-(num-ah); //a의 위치 구하기

ah를 1씩 올리면서 num과 더하고, num이 a보다 크거나 같아질 때를 찾는다.

같은 알고리즘을 활용해서 a의 높이, a의 위치,b의 높이, b의 위치를 구한다.

 

피라미드 좌표의 위치는 

while(num<a) { num=num+ah; ah++; //a의 높이 구하기 }
ah=ah-1; aw=a-(num-ah); //a의 위치 구하기

 

5를 예시로 들면, 마지막 num은 그 층의 가장 큰 숫자(6)가 된다.

그 숫자에서 현재의 높이(3)를 빼면 바로 위층의 마지막 숫자(3)가 나온다.

그 숫자를 기준으로 몇번째 숫자인지를 구해주면 된다.

ex) 5-(6-3)=2(그 층에서 몇번째 숫자인지가 나옵니다) 구하려는 위치-위층 마지막 숫자

 

범위가 높이 안쪽이면 대각선으로 움직일 수가 있기때문에 옆으로 움직이는 값을 굳이 생각해주지 않아도 된다.

1

2 3

3 4 5

6 7 8 9

10 11 12 13 14 ...

모양으로 순서를 부여해줬기 때문에, aw보다 bw가 작다면  |aw-bw| 값만 더해주고, 

aw보다 bw가 크다면  |aw-bw| 값에 높이를 빼준 값을 더해준다.

 

역삼각형모양을 고려해주는 알고리즘을 생각하는 것보다, a와 b를 바꿔주는 것이 효율적일 것 같아서 a가 b보다 크다면 a와 b를 바꿔주었다.

rh = Math.abs(ah-bh); 
if(aw<=bw) {
				if(Math.abs(aw-bw)>rh) {
					rw=Math.abs(aw-bw)-rh;
				}	
			}
else {
				rw=Math.abs(aw-bw);
			}

 

코드

---

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

public class Solution{
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		int T = Integer.parseInt(st.nextToken());
		for(int test=0; test<T; test++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			
			int temp=0;
			if(a>b) { //a와 b바꿔주기
				temp=a;
				a=b;
				b=temp;
			}
			
			int num=0;
			int ah=0;
			int aw=0;
			while(num<a) {
				num=num+ah;
				ah++; //a의 높이 구하기
			}
			
			ah=ah-1;
			aw=a-(num-ah); //a의 위치 구하기
			
			num=0;
			int bh=0;
			int bw=0;
			while(num<b) {
				num=num+bh;
				bh++; //b의 높이 구하기
			}
			
			bh=bh-1;
			bw=b-(num-bh); //b의 위치 구하기
			
			int result=0;
			int rh=0;
			int rw=0;
			rh = Math.abs(ah-bh); //a, b 높이의 차 구하기
			
			if(aw<=bw) {
				if(Math.abs(aw-bw)>rh) {
					rw=Math.abs(aw-bw)-rh;
				}	
			}
			else {
				rw=Math.abs(aw-bw);
			}
			
			result=rh+rw;
			
			
			System.out.printf("#%d %d",test+1,result);
			System.out.println();
		}
		
		
	}
	
	
}