[10250] ACM호텔
시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율
1 초 | 256 MB | 206413 | 70967 | 59869 | 33.316% |
문제
ACM 호텔 매니저 지우는 손님이 도착하는 대로 빈 방을 배정하고 있다. 고객 설문조사에 따르면 손님들은 호텔 정문으로부터 걸어서 가장 짧은 거리에 있는 방을 선호한다고 한다. 여러분은 지우를 도와 줄 프로그램을 작성하고자 한다. 즉 설문조사 결과 대로 호텔 정문으로부터 걷는 거리가 가장 짧도록 방을 배정하는 프로그램을 작성하고자 한다.
문제를 단순화하기 위해서 호텔은 직사각형 모양이라고 가정하자. 각 층에 W 개의 방이 있는 H 층 건물이라고 가정하자 (1 ≤ H, W ≤ 99). 그리고 엘리베이터는 가장 왼쪽에 있다고 가정하자(그림 1 참고). 이런 형태의 호텔을 H × W 형태 호텔이라고 부른다. 호텔 정문은 일층 엘리베이터 바로 앞에 있는데, 정문에서 엘리베이터까지의 거리는 무시한다. 또 모든 인접한 두 방 사이의 거리는 같은 거리(거리 1)라고 가정하고 호텔의 정면 쪽에만 방이 있다고 가정한다.
방 번호는 YXX 나 YYXX 형태인데 여기서 Y 나 YY 는 층 수를 나타내고 XX 는 엘리베이터에서부터 세었을 때의 번호를 나타낸다. 즉, 그림 1 에서 빗금으로 표시한 방은 305 호가 된다.
손님은 엘리베이터를 타고 이동하는 거리는 신경 쓰지 않는다. 다만 걷는 거리가 같을 때에는 아래층의 방을 더 선호한다. 예를 들면 102 호 방보다는 301 호 방을 더 선호하는데, 102 호는 거리 2 만큼 걸어야 하지만 301 호는 거리 1 만큼만 걸으면 되기 때문이다. 같은 이유로 102 호보다 2101 호를 더 선호한다.
여러분이 작성할 프로그램은 초기에 모든 방이 비어있다고 가정하에 이 정책에 따라 N 번째로 도착한 손님에게 배정될 방 번호를 계산하는 프로그램이다. 첫 번째 손님은 101 호, 두 번째 손님은 201 호 등과 같이 배정한다. 그림 1 의 경우를 예로 들면, H = 6이므로 10 번째 손님은 402 호에 배정해야 한다.
입력
프로그램은 표준 입력에서 입력 데이터를 받는다. 프로그램의 입력은 T 개의 테스트 데이터로 이루어져 있는데 T 는 입력의 맨 첫 줄에 주어진다. 각 테스트 데이터는 한 행으로서 H, W, N, 세 정수를 포함하고 있으며 각각 호텔의 층 수, 각 층의 방 수, 몇 번째 손님인지를 나타낸다(1 ≤ H, W ≤ 99, 1 ≤ N ≤ H × W).
출력
프로그램은 표준 출력에 출력한다. 각 테스트 데이터마다 정확히 한 행을 출력하는데, 내용은 N 번째 손님에게 배정되어야 하는 방 번호를 출력한다.
처음 문제풀이
0. TestCase와 건물의 높이, 넓이, 손님 번호 입력
이 문제는 TestCase가 존재한다. 한번의 예제만 입력을 받는 것이 아닌 여러 케이스를 한번에 입력 받는 것! 입력을 받기 위해 BufferedReader와 BufferedWriter를 사용했다. 이번 문제는 Scanner를 사용해도 시간 제한을 초과하지 않지만 더 빠르게 입력하고 출력할 수 있는 방법에 익숙하기 위해 Buffer 사용했다.
Scanner를 사용했을때 시간이 120ms가 나왔고 Buffer를 사용햇을때 88ms가 나왔다.
1. 101~H01까지 순차적으로 방에 입장하고 H까지 입장이 되면 201~20W까지 순차적으로 입장
이 문제의 조건은 손님이 걷는 것을 싫어한다. 걷는 거리가 같을때는 아랫방을 선호한다. 라는 조건이 있다. 즉 H01부터 입장을 하면 되고 걷는 것이 같다면 10W가 된다. 즉. H0W번호를 배정 받는다.
2. N번째 손님 입장시 배정받은 방번호 출력
반복을 하며 방을 배정할때 N번째 반복을 하게 된다면 반복을 멈추고 손님을 출력하면 된다.
전체 코드
import java.io.*;
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));
int T = Integer.parseInt(br.readLine());
/// 1. TestCase 입력
while (T --> 0) {
/// 2. 건물의 높이, 넓이 , 손님 번호 입력
String[] input = br.readLine().split(" ");
int H = Integer.parseInt(input[0]);
int W = Integer.parseInt(input[1]);
int N = Integer.parseInt(input[2]);
int ans = 0;
int number = 0;
boolean isFindAnswer = false;
/// 3. 선형적으로 1~H까지 순차적으로 증가 후 i가 H랑 값이 같으면 W 증가
for(int w=1; w<=W; w++) {
if (!isFindAnswer) {
for (int h = 1; h <= H; h++) {
if (!isFindAnswer) {
ans = (h * 100 + w);
number++;
if (number == N) {
bw.write(String.valueOf(ans) + "\\n");
isFindAnswer = true;
}
}
}
}
}
bw.flush();
}
}
}
시간복잡도
이 알고리즘의 시간복잡도는 **O(n^2)**이다.
두번째 문제풀이
처음 문제풀이의 시간복잡도를 보면 **O(n^2)**이다. 별로 좋지 않은 시간복잡도이기 때문에 개선하여 문제를 풀어보자.
1. 차례로 배정해보자.
손님은 항상 1층 1호 부터 배정을 받는다. 이 명제를 따라 알고리즘을 작성해보겠다.
int floor = 1; // 배정받을 방의 층 수
int distance = 1; // 엘레베이터의 거리
while(--N > 0) { // 101호를 배치한 상태이므로 N-1번만 진행
floor++; // 새 손님에게 이전방보다 높은 방 제공
if(floor>N){
floor = 1; // 해당 distance의 방이 모두 배정되었다면
distance++; // 다음 distance의 가장 낮은 층을 배정.
}
}
2. 한번에 계산해보자.
W = 12, H = 10인 호텔을 기준으로 계산을 해보자.
110 번째 손님과 111번째 손님의 방은?
110 : 1011호, 111: 112호
즉, 한 방씩 배치하지 않아도 10명마다 엘레베이터와 한 칸 씩 멀어지는 것을 알 수 있다.
N번째 손님의 호 수: H로 나눈 몫 1~H ⇒ 1, H+1~2H⇒ 2 : (110 -1) % 10 + 1
N번째 손님의 층 수: H로 나눈 나머지 [0, H~1] ⇒ [1, H] : (110-1) / 10 + 1
import java.util.Scanner;
class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
while(T-->0) {
int H = sc.nextInt();
int W = sc.nextInt();
int N = sc.nextInt();
int distance = (N - 1) / H + 1;
int floor = (N - 1) % H + 1;
System.out.printf("%d%02d\\n", floor, distance);
}
}
}
시간복잡도
이 알고리즘의 시간복잡도는 O(1)이다.
[1730] 판화
시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율
2 초 | 128 MB | 2948 | 1061 | 875 | 36.428% |
문제
W대학교 미술대학 조소과에서는 지루한 목판화 작업을 하는 학생들을 돕기 위해 판화 기계를 제작하였다.
기계는 로봇 팔이 쥔 조각도를 상하좌우 네 방향으로 움직일 수 있는 구조로서, 조각도 아래에 목판을 놓으면 그 위에 선들을 자동으로 그어주는 기능을 가지고 있다.
목판에는 N2개의 점들이 일정한 간격으로 N행 N열의 격자모양을 이루며 찍혀있다. 처음 로봇의 조각도를 올려놓는 위치는 항상 이 점들 중 맨 왼쪽 맨 위의 꼭짓점이다.
로봇 팔을 움직이는 명령의 순서가 주어졌을 때, 목판 위에 패인 조각도의 혼적을 출력하는 프로그램을 작성하시오.
판화 기계는 작동 도중 로봇 팔이 격자 바깥으로 나가도록 하는 움직임 명령을 만나면, 무시하고 그 다음 명령을 진행한다.
입력
첫째 줄에 목판의 크기 N (2 ≤ N ≤ 10)이 주어진다. 행 열의 점들이 찍혀 있다는 의미이다. 둘째 줄에 로봇팔의 움직임이 한 줄로 공백 없이 입력된다. 위쪽으로 이동은 'U', 아래쪽으로 이동은 'D', 왼쪽으로 이동은 'L', 오른쪽으로 이동은 'R'로 표시된다. 로봇팔의 움직임을 나타내는 이 문자열의 길이는 최대 250이다.
출력
로봇팔이 지나지 않은 점은 '.'으로, 로봇팔이 수직 방향으로만 지난 점은 '|'으로, 로봇팔이 수평 방향으로만 지난 점은 '-'으로, 수직과 수평 방향 모두로 지난 점은 '+'로 표기하도록 한다. 네 문자의 ASCII 코드는 각각 46, 124, 45, 43이다.
문제풀이
1. 팔을 명령 순서대로 움직인다.
1-1. D: 아래로 움직일 수 있다면 지금 칸과 다음칸에 세로 흔적을 남긴다.
if(cmd == 'D') {
if (curR == N -1 ) continue;; // 마지막에 위치한다면 명령을 무시.
// 지금 이동할 칸과 다음 이동할 칸의 흔적(true) 남김.
passVertical[curR][curC] = passViertical[curR + 1][curC] = true;
curR++;
}
1-2. U: 위로 움직일 수 있다면 지금 칸과 다음 칸에 세로 흔적을 남긴다.
if(cmd == 'U') {
if (curR == 0) continue;; // 마지막에 위치한다면 명령을 무시.
// 지금 이동할 칸과 다음 이동할 칸의 흔적(true) 남김.
passVertical[curR][curC] = passViertical[curR - 1][curC] = true;
curR--;
}
1-3. L: 왼쪽으로 움직일 수 있다면 지금 칸과 다음 칸에 가로 흔적을 남긴다.
if(cmd == 'L') {
if (curC == 0) continue;; // 마지막에 위치한다면 명령을 무시.
// 지금 이동할 칸과 다음 이동할 칸의 흔적(true) 남김.
passHorizontal[curR][curC] = passHorizontal[curR][curC - 1] = true;
curC--;
}
1-4. R: 오른쪽으로 움직일 수 있다면 ㅍ지금 칸과 다음 칸에 가로 흔적을 남긴다.
if(cmd == 'R') {
if (curC == N - 1) continue;; // 마지막에 위치한다면 명령을 무시.
// 지금 이동할 칸과 다음 이동할 칸의 흔적(true) 남김.
passHorizontal[curR][curC] = passHorizontal[curR][curC + 1] = true;
curC++;
}
2. 누적된 흔적을 출력한다.
만약 Vertical, Horizontal 요소 안에 true값이 라면 +를 출력
Vertical만 있다면 “|” 출력, Horizontal만 있다면 “-” 출력
그것도 아니라면 “.” 을 출력한다.
여기서 로봇팔의 움직임을 나타내는 이 문자열의 길이는 최대 250이라는 조건이 있다.
이 조건은 즉 문자열 길이가 0으로 들어올 수 도 있다는 예제기 때문에 sc.hasNext() 함수를 이용하였다.
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
String command = sc.hasNext() ? sc.next() : "";
boolean[][] passViertical = new boolean[N][N]; // 세로로 경유한 적이 있는가?
boolean[][] passHorizontal = new boolean[N][N]; // 가로로 경유한 적이 있는가?
int curR = 0, curC = 0; // 로봇 팔의 위치
for (int i =0; i<N; i++) {
String ans = "";
for (int j=0; j<N; j++) {
if (passViertical[i][j] && passHorizontal[i][j]) ans += "+";
else if (passViertical[i][j]) ans += "|";
else if (passHorizontal[i][j]) ans += "-";
else ans += ".";
}
System.out.println(ans);
}
전체코드
import java.util.Scanner;
class Main {
public static void main(String[] args) {
/// 1. 입력받기
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
String command = sc.hasNext() ? sc.next() : "";
int curR = 0, curC = 0;
boolean[][] passViertical = new boolean[N][N]; // 세로로 경유한 적이 있는가?
boolean[][] passHorizontal = new boolean[N][N]; // 가로로 경유한 적이 있는가?
for(int i = 0; i<command.length(); i++) {
char cmd = command.charAt(i);
if (cmd == 'D') {
if (curR == N - 1) continue;
passViertical[curR][curC] = passViertical[curR + 1][curC] = true;
curR++;
} else if (cmd == 'U') {
if (curR == 0) continue;
passViertical[curR][curC] = passViertical[curR - 1][curC] = true;
curR--;
} else if (cmd == 'L') {
if (curC == 0) continue;
passHorizontal[curR][curC] = passHorizontal [curR][curC - 1] = true;
curC--;
} else {
if (curC == N-1) continue;
passHorizontal[curR][curC] = passHorizontal[curR][curC + 1 ] = true;
curC++;
}
}
for (int i =0; i<N; i++) {
String ans = "";
for (int j=0; j<N; j++) {
if (passViertical[i][j] && passHorizontal[i][j]) ans += "+";
else if (passViertical[i][j]) ans += "|";
else if (passHorizontal[i][j]) ans += "-";
else ans += ".";
}
System.out.println(ans);
}
}
}
시간복잡도
명령어를 입력 받을 때 에는 O(L)
흔적을 출력할때는 O(N^2)
O(max(N^2, L)이다.
'알고리즘 > Brute Force' 카테고리의 다른 글
[코딩테스트] [2840] 행운의 바퀴 & [2817] ALPS식 투표 (0) | 2024.12.05 |
---|---|
[코딩테스트] [11068] 회문인 수 & [3085] 사탕게임 (0) | 2024.12.03 |
[코딩테스트] (완전탐색,시뮬레이션) & [10448] 유레카 이론 & [11005] 진법 변환2 (0) | 2024.12.03 |
[백준/Silver V] 셀프 넘버 - 4673 (0) | 2024.05.24 |