두부의 코딩일기

https://www.acmicpc.net/problem/9576 9576번: 책 나눠주기 백준이는 방 청소를 하면서 필요 없는 전공 서적을 사람들에게 나눠주려고 한다. 나눠줄 책을 모아보니 총 N권이었다. 책이 너무 많기 때문에 백준이는 책을 구분하기 위해 각각 1부터 N까지의 www.acmicpc.net 🔶 풀이 그리드 알고리즘으로 충분히 해결할 수 있는 문제. 1번부터 N번까지의 책을 가지고 있고, a부터 b까지 중 하나의 책을 최대한 많은 학생에게 나눠주면 된다. 중복된 책을 나눠주면 안되기 때문에 book 배열로 나눠줌 여부를 판단해줬다. 문제를 잘 살펴보면 한 가지 예외가 있다. 1 5 4 1 5 // 1번 책을 나눔 2 5 // 2번 책을 나눔 3 4 // 3번 책을 나눔 3 3 위의 예제를..

https://www.acmicpc.net/problem/19640 19640번: 화장실의 규칙 위와 같이 줄을 선 경우를 생각해보자. (x, y) 는 사원의 근무 일수가 x, 화장실이 급한 정도가 y임을 나타낸다. [x, y]는 해당 사원이 데카임을 의미한다. 즉, 위의 그림에서 데카는 3번 사원이다. www.acmicpc.net 🔶 풀이 각 줄에서 맨 앞에 있는 사람끼리 비교해야하는 문제. 1. M개의 줄로 나눠서 WaitLine 배열리스트에 사원들을 입력해준다. ArrayList[] waitLine = new ArrayList[M]; for (int i=0; i

https://www.acmicpc.net/problem/2146 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net 🔶 풀이 "섬에서 섬으로 건너갈 수 있는 가장 짧은 다리의 길이는?" 가장 먼저 해야할 건 각각의 섬에 다른 번호를 매겨주는 것이다. 여러 개의 섬이 존재하는데 번호가 같으면 bfs를 이용해서 다른 섬을 찾아가는 게 힘들다. public static void setLand (int x, int y, int num) { Queue q = new LinkedList(); q.add(new Pos(x, y,..

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..

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

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/7568 7568번: 덩치 우리는 사람의 덩치를 키와 몸무게, 이 두 개의 값으로 표현하여 그 등수를 매겨보려고 한다. 어떤 사람의 몸무게가 x kg이고 키가 y cm라면 이 사람의 덩치는 (x, y)로 표시된다. 두 사람 A 와 B의 덩 www.acmicpc.net 풀이 브루트포스를 이용해서 푸는 문제다. '각 사람의 덩치 등수는 몇 등인가?' 문제에서의 덩치가 큰 기준은 키와 몸무게가 모두 비교하는 대상보다 클 경우다. 키와 몸무게를 담을 수 있는 배열을 생성 후에 2중 for문을 이용해서 본인을 제외한 모두와 비교하여 rank 값을 출력해줬다. 문제에서 rank는 본인보다 덩치가 큰 사람 수 + 1 이기 때문에 rank 변수는 1로 초기화해주..