두부의 코딩일기

https://www.acmicpc.net/problem/14499 14499번: 주사위 굴리기 첫째 줄에 지도의 세로 크기 N, 가로 크기 M (1 ≤ N, M ≤ 20), 주사위를 놓은 곳의 좌표 x, y(0 ≤ x ≤ N-1, 0 ≤ y ≤ M-1), 그리고 명령의 개수 K (1 ≤ K ≤ 1,000)가 주어진다. 둘째 줄부터 N개의 줄에 지 www.acmicpc.net 🔶 풀이 모든 면이 0으로 채워진 주사위를 굴렸을 때 발생하는 일은 아래와 같다. 1. 이동한 칸에 쓰여 있는 수가 0인 경우, 주사위의 바닥면에 쓰여 있는 수를 복사한다. 2. 이동한 칸에 쓰여 있는 수가 0이 아닌 경우, 칸에 쓰여있는 수가 주사위의 바닥면에 복사되고, 칸은 0이 된다. 주사위는 지도의 크기에서 벗어날 수 없고,..

https://www.acmicpc.net/problem/1966 1966번: 프린터 큐 여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 www.acmicpc.net 🔶 풀이 Queue로 중요도만 체크해 주면 되는 간단한 문제다. 모든 문서를 FIFO 형식인 Queue에 입력해 놓고 중요도가 높은 것부터 순서대로 뽑아내면 된다. 언뜻 보면 정렬로 빠르게 뽑아낼 수 있을 것 같지만 중복된 중요도가 있을 수 있기 때문에 정렬로는 해결할 수 없다. 즉, Queue의 특성을 이용해서 해결해야 한다. 맨 앞에 있는 문서보다 중요도가 높은 문서가 있으면 맨 앞의 문서를 뒤로..

10431번: 줄세우기 (acmicpc.net) 10431번: 줄세우기 초등학교 선생님 강산이는 아이들을 데리고 단체로 어떤 일을 할 때 불편함이 없도록 새로 반에 배정받은 아이들에게 키 순서대로 번호를 부여한다. 번호를 부여할 땐 키가 가장 작은 아이가 1 www.acmicpc.net 풀이 "줄서기가 끝났을 때 학생들이 총 몇 번 뒤로 물러서게 될까?" 줄 서는 조건이 거창하지만 엄청 쉬운 문제였다. 반복문으로 앞에 키 큰 사람이 몇 명인지 세주면 간단하게 해결할 수 있다. import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedRea..

2075번: N번째 큰 수 (acmicpc.net) 2075번: N번째 큰 수 첫째 줄에 N(1 ≤ N ≤ 1,500)이 주어진다. 다음 N개의 줄에는 각 줄마다 N개의 수가 주어진다. 표에 적힌 수는 -10억보다 크거나 같고, 10억보다 작거나 같은 정수이다. www.acmicpc.net 풀이 N*N 크기의 2차원 배열에서 N번째 큰 수를 찾으면 된다. 우선순위 큐를 사용하면 쉽게 해결할 수 있다. 기본적으로 오름차순으로 정렬되기 때문에 N번째 큰 수를 찾기 위해서는 정렬을 재정의해주어야 한다. 단순 integer형 큐이기 때문에 Collections.reverseOrder() 를 사용해서 역순으로 정렬해 주었다. 이후에 N-1번째까지 pq.poll()을 해주고, pq.poll()을 한 번 더 사용해서..

1244번: 스위치 켜고 끄기 (acmicpc.net) 1244번: 스위치 켜고 끄기 첫째 줄에는 스위치 개수가 주어진다. 스위치 개수는 100 이하인 양의 정수이다. 둘째 줄에는 각 스위치의 상태가 주어진다. 켜져 있으면 1, 꺼져있으면 0이라고 표시하고 사이에 빈칸이 하나씩 www.acmicpc.net 풀이 딱히 풀이라고 할 게 없는 문제다. 그냥 문제에서 시키는대로 해주면 된다. 번호가 주어졌을 때 남학생일 경우 번호의 배수에 해당하는 스위치 상태를 변경해주면 된다. 예를 들어 3이 주어졌다면 3, 6, 9, ··· 를 변경해준다. 여학생일 경우 번호의 양 옆 스위치 상태를 확인하고 서로 다를 때까지 비교해준다. 두 개의 스위치 값이 같다면 변경해주고, 다르면 탐색을 중단한다. 예를 들어 3이 주어..

https://www.acmicpc.net/problem/20926 20926번: 얼음 미로 탐험가 테라는 얼음 미로에 갇혔다. 얼음 미로의 바닥은 빙판으로 되어 있어 발을 내디디면 바위에 부딪힐 때까지 미끄러진다. 예를 들어, 위 그림에서 테라가 왼쪽 방향으로 이동한다면 중간에 www.acmicpc.net 풀이 포켓몬 얼음동굴이 생각나는 다익스트라 문제. 테라, 바위, 구멍, 출구가 char형이라서 int형으로 임의의 값을 줘서 int형 배열로 선언했다. static int Rock = 100, Hole = -1, Escape = 200, W, H; for (int i=0; i= W) break; if (map[nx][ny] == Hole) break; if (map[nx][ny] == Rock) { ..

https://www.acmicpc.net/problem/1106 1106번: 호텔 첫째 줄에 C와 형택이가 홍보할 수 있는 도시의 개수 N이 주어진다. C는 1,000보다 작거나 같은 자연수이고, N은 20보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 각 도시에서 홍보할 때 www.acmicpc.net 풀이 "호텔의 고객을 적어도 C명 늘리기 위해 형택이가 투자해야하는 돈의 최솟값을 구하시오." 문제 요구사항에서 주목해야할 건 "적어도 C명"이다. 만약 목표치가 10명인데 11명, 12명을 모집했을 때가 더 비용이 적게 든다면 그 비용을 출력해야한다. 예제 2번을 보면 쉽게 이해할 수 있다. 3명 모집 -> 1원 6명 모집 -> 2원 9명 모집 -> 3원 10명 모집 -> 6원 11명 모집 ..

https://www.acmicpc.net/problem/11067 11067번: 모노톤길 입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 테스트 데이터의 개수 T가 정수로 주어진다. 각 테스트 데이터의 첫 번째 줄에는 카페의 수 www.acmicpc.net 풀이 제한 시간이 5초로 엄청 길고, n의 범위가 최대 100,000 이므로 T의 값에 따라서 완전 탐색도 충분히 가능하다고 본다. 문제 조건에는 "x축의 값이 작아지는 경우는 없어도 출구까지 도달할 수 있다." 이다. 따라서 카페 방문 순서는 아래와 같다. 1. 현재 위치와 같은 x축에 있는 카페들 중 가까운 카페부터 방문한다. 2. 현재 위치와 같은 x축의 카페를 모두 방문했다면 y축이 동일한 ..

https://www.acmicpc.net/problem/14503 14503번: 로봇 청소기 첫째 줄에 방의 크기 $N$과 $M$이 입력된다. $(3 \le N, M \le 50)$ 둘째 줄에 처음에 로봇 청소기가 있는 칸의 좌표 $(r, c)$와 처음에 로봇 청소기가 바라보는 방향 $d$가 입력된다. $d$가 $0$인 경우 북쪽 www.acmicpc.net 풀이 로봇 청소기의 작동 과정을 딱 보고 굳이 3-3번에서 1번으로 돌아가야되나? 싶었다. 한 문장으로 작동 과정을 적어보면 아래와 같다. "현재 위치를 청소 후, 왼쪽으로 돌면서 청소되어 있지 않은 곳을 발견하면 그 방향으로 한 칸 전진하고, 한 바퀴를 다 돈 후에도 청소할 곳이 없다면 후진한다." 후진을 할 경우에 뒤에 벽이 있다면 그대로 종료..

https://www.acmicpc.net/problem/15684 15684번: 사다리 조작 사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선 www.acmicpc.net 풀이 입력하는 과정에서 가로선 정보를 2차원 배열 map[][]에 3가지 경우로 나눠서 입력해줬다. 0: 해당 칸에는 가로선이 없음 1: 해당 칸에서 오른쪽으로 연결되는 선이 존재함 2: 해당 칸에서 왼쪽으로 연결되는 선이 존재함 해당 문제는 3개 이하의 가로선을 만들어서 i번에서 출발하면 i번으로 도착하게 만드는 문제다. 3개 이하의 가로선을 만들어야하기 때문에 dfs를 돌릴 때 limit 함..