문제 탐색하기
입력 자료 정리
- width는 블록의 가로 길이, height는 블록의 세로길이이다
- n은 상점의 개수를 의미한다
- 이후 들어오는 값들은 첫번째는 방향이며 두번째는 그 방향에서의 위치다
- 방향은 1은 y가 0일때, 2는 y가 height일때, 3은 x가 0일때, 4는 x가 height일때다
- 마지막에 값이 한번더 들어오는데 이것은 동근이의 위치이며,
들어오는 값은 장소의 값과 같은 형식으로 들어온다
해결방법 추론
- 이 문제는 그냥 구현으로 푸는 문제다. 다만 조건이 많아 잘 고려하여 풀어야한다
- 먼저 좌표에 대한 입력값도 평범한 방식이 아니라서 조금 구분지어서 풀어내야한다
- 첫 입력값은 1,2,3,4로 한정되므로 각 경우에 따라조건을 분기하여
x값을 새로운 값으로 만들어내야한다 - y,x좌표로 만들어 관리할까도 생각했는데, 그러면 if문을 엄청 쓰게 될 것 같아
다른 방법을 생각하였다 - 0,0인 지점을 좌상으로 잡고 시계방향으로 돌았을 때,
그 지점까지의 거리로 값을 가공하는 방법을 생각하였다 - 1인 경우는 윗줄이므로 그대로 x를 넣어주고,
4인 경우는 오른쪽 줄이므로 가로길이인 width에다가 height - x한 값을 넣어준다
2인 경우는 아랫줄이고 3인경우는 왼쪽 줄이므로 각각 height과 width를 한번 더 더해서
새롭게 값을 만들어낸다 - 그런다음 건물과 동근이의 거리의 차이를 구해서,
그 차이와 전체길이에서 뺀 값중 더 작은 값을 더한다면 최단거리의 합이 될 것이라 생각했다
시간복잡도 계산
- 시간복잡도는 간단하다 건물의 수만큼 탐색하면 되므로 n만큼의 연산이 발생한다
- 따라서 시간복잡도는 O(n)이 되며, 시간제한안에 문제를 해결할 수 있다
코드 설계하기
입력값 상태 관리
- 입력값은 int형 1차원 배열에 관리한다. 이때, 크기는 n만큼으로 한다.
- 동근이는 별도로 변수를 만들어서 관리하며, 정답 출력을 위한 ans도 변수로 관리한다
구현 설계
- 앞서 추론한 방법대로 입력값을 가공하고,
n만큼 탐색을 통해 동근이와 건물간의 차이와 전체 길이에서 그 차이를 뺀 값중
작은 값을 더해나가면 최단거리의 합을 구할 수 있을 것이다. - 그 합은 ans에 더해준다
출력값 설계
- 완성한 ans를 출력하면 정답이 될텐데..
시도회차 수정
1회차 시도 실패
- 3%에서 틀려버렸다...
- 코드를 짜면서 중복되는 부분도 있었기에 코드를 재편하면서 다시 시도해보려고 한다
원인 분석
- 일단 동근이를 int형 배열에다가 넣어주었다
- 변수로 관리할 필요없이 int형 배열의 크기를 하나 늘려주면 되기 때문에,
중복되는 스위치문도 없애고 더 관리도 편하게 하기 위해서 변경하였다 - 이어서 틀린부분도 다시 찾기 위해 코드를 다시 읽었다
- 문제가 되는 부분은 바로 case 4에서 였다
- 거리 계산을 윗줄에서 내려가는 방향으로 하면 x를 그냥 더해주면 되는데
height-x로 잘못 생각하여 틀리는 문제였다 - 따라서 해당 부분을 고치고 다시 제출하였다
2회차 시도 성공
- 제출 후 바로 정답이 되었다!
정답 코드
(1회차 시도 실패)
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
int width = Integer.parseInt(st.nextToken());
int height = Integer.parseInt(st.nextToken());
int n = Integer.parseInt(br.readLine());
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
int y = Integer.parseInt(st.nextToken());
int x = Integer.parseInt(st.nextToken());
switch (y){
case 1:
arr[i] = x;
break;
case 4:
arr[i] = width + (height - x);
break;
case 2:
arr[i] = width + height + (width - x);
break;
case 3:
arr[i] = 2*width + height + (height - x);
break;
}
}
st = new StringTokenizer(br.readLine());
int y = Integer.parseInt(st.nextToken());
int x = Integer.parseInt(st.nextToken());
int dong = 0;
switch (y){
case 1:
dong = x;
break;
case 4:
dong = width + (height - x);
break;
case 2:
dong = width + height + (width - x);
break;
case 3:
dong = 2*width + height + (height - x);
break;
}
int ans = 0;
for (int i = 0; i < n; i++) {
int sum = Math.abs(dong - arr[i]);
ans += Math.min(sum, (width*2 + height*2) - sum);
}
bw.write(ans+"");
br.close();
bw.close();
}
}(2회차 시도 성공)
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
int width = Integer.parseInt(st.nextToken());
int height = Integer.parseInt(st.nextToken());
int n = Integer.parseInt(br.readLine());
int[] arr = new int[n+1];
for (int i = 0; i < n+1; i++) {
st = new StringTokenizer(br.readLine());
int y = Integer.parseInt(st.nextToken());
int x = Integer.parseInt(st.nextToken());
switch (y){
case 1:
arr[i] = x;
break;
case 4:
arr[i] = width + x;
break;
case 2:
arr[i] = width + height + (width - x);
break;
case 3:
arr[i] = 2*width + height + (height - x);
break;
}
}
int ans = 0;
for (int i = 0; i < n; i++) {
int sum = Math.abs(arr[n] - arr[i]);
ans += Math.min(sum, (width + height)*2 - sum);
}
bw.write(ans+"");
br.close();
bw.close();
}
}
문제 링크
Software Developer