[구름/구현] 인공지능 청소기

문제

https://level.goorm.io/exam/43068/1a-%EC%9D%B8%EA%B3%B5%EC%A7%80%EB%8A%A5-%EC%B2%AD%EC%86%8C%EA%B8%B0/quiz/1

구름LEVEL

 

해결방법

해당 문제를 처음 읽었을때는, BFS로 해결 가능한 문제라고 생각했다. 그러나 입력값의 조건에 의하면 2 * 10^9이기때문에, 이는 무조건 메모리초과가 발생하기때문에 새로운 방법이 필요했다. 문제에서 조건으로 한칸씩이동, 중복이동 가능의 특성을 고려하면 짝수번째 이동했을때는 좌표의 절대값의 합이 짝수번째 칸에 위치하고, 홀수번째 이동했을때는 홀수번째 칸에 위치한다. 이를 코드로 구현하면 시간초과와 메모리초과가 발생하지 않게 해결할 수 있다.

 

소스코드

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

class Main {
	static int n;
	static StringBuilder answerBuilder = new StringBuilder();
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine());

		for(int i = 0; i < n; i++){
			String[] line = br.readLine().split(" ");
			int goalX = Math.abs(Integer.parseInt(line[0]));
			int goalY = Math.abs(Integer.parseInt(line[1]));
			int t = Integer.parseInt(line[2]);
			int goalSum = goalX + goalY;
			
			if(goalSum > t){
				answerBuilder.append("NO\n");
				continue;
			}
			if(goalSum % 2 != t % 2){
				answerBuilder.append("NO\n");
				continue;
			}
				answerBuilder.append("YES\n");
		}
		
		System.out.println(answerBuilder.toString());
	}
}