두부의 코딩일기

https://www.acmicpc.net/problem/13460 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net 풀이 생각했던 것보다 오래 걸렸던 문제였다. 위 문제에는 빨간 구슬과 파란 구슬 두 가지가 존재한다. 핵심은 빨간 구슬이 10번 이하로 움직여서 구멍에 들어가야한다. 또한, 빨간 구슬과 파란 구슬이 동시에 들어가면 안된다. 한 번의 움직임에 한 방향으로 벽이 나타날때까지 계속 움직일 수 있다. 빨간 구슬을 예로 살펴보겠다. // 빨간 구슬 int ..

https://www.acmicpc.net/problem/14890 14890번: 경사로 첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다. www.acmicpc.net 풀이 처음에 문제를 잘 못 이해해서 꽤 오랫동안 고민했다. 우선 모든 행과 열을 한 줄로 나열해서 체크해야 한다. 예를 들어, 위 그림처럼 6x6 행렬이 있다면 행 6번, 열 6번 총 12번의 체크를 해야 한다. for (int i=0; i 1) { return false; } 이젠 경사로를 놓았을 때의 경우만 생각하면 된다. 경사로를 놓았을 때 생기는 경우의 수는 2가지이다. 오르막 길 내리막 길 오르막 길, 내리막 ..

https://www.acmicpc.net/problem/17144 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net 풀이 문제에 이해하기 쉽게 설명이 잘 적혀있으니까 생략하겠다. 위 문제에서는 두 개의 일이 순서대로 이루어진다. 미세먼지 확산: 4방향으로 먼지가 확산된다. 공기청정기 작동: 위 칸과 아래 칸의 바람이 방향이 서로 다르며 한 칸씩 먼지를 밀어낸다. 미세먼지 확산은 dfs 혹은 bfs를 이해하고 있고 관련된 문제를 풀어봤다면 쉽게 해결할 수 있을 것이다. public static void Dust..

https://www.acmicpc.net/problem/15683 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net 풀이 5가지의 감시 카메라가 상우하좌로 돌면서 사각지대의 최솟값을 찾아야한다. 감시 카메라의 경우의 수는 아래와 같다. 1번 카메라: 4가지 2번 카메라: 2가지 3번 카메라: 4가지 4번 카메라: 4가지 5번 카메라: 1가지 예를 들어 1번과 2번 카메라가 하나씩 존재한다면 경우의 수는 4 x 2 = 8가지이다. 경우의 수를 다 돌려주기 위해서 완전탐색 dfs를 돌려준다. public..

https://www.acmicpc.net/problem/10773 10773번: 제로 첫 번째 줄에 정수 K가 주어진다. (1 ≤ K ≤ 100,000) 이후 K개의 줄에 정수가 1개씩 주어진다. 정수는 0에서 1,000,000 사이의 값을 가지며, 정수가 "0" 일 경우에는 가장 최근에 쓴 수를 지우고, 아닐 경 www.acmicpc.net 풀이 문제의 조건은 매우 간단하다. 0이 등장하면 전에 입력받았던 숫자를 지우면 된다. 또한, 0이 등장했을 땐 지울 수 있는 숫자가 있음을 보장했기 때문에 예외 처리를 해줄 필요도 없다. 문제를 푸는 방법은 2가지가 있다. 1. 스택 (Stack) 을 이용하는 방법 import java.io.*; import java.util.*; public class Mai..

https://www.acmicpc.net/problem/1913 1913번: 달팽이 N개의 줄에 걸쳐 표를 출력한다. 각 줄에 N개의 자연수를 한 칸씩 띄어서 출력하면 되며, 자릿수를 맞출 필요가 없다. N+1번째 줄에는 입력받은 자연수의 좌표를 나타내는 두 정수를 한 칸 띄어서 www.acmicpc.net 풀이 실버3 난이도의 구현 문제로 생각보다 오래 걸렸다... 문제를 시작하기에 앞서 시작 위치와 방향 전환에 대해서 고민해봐야 한다. 우선 왼쪽 그림처럼 (0, 0) 을 시작점으로 두고 시작하게 되면 숫자가 1씩 작아지고, 오른쪽 그림처럼 (N/2, N/2) 에서 시작하게 되면 숫자가 1씩 증가한다. 또한 나아가는 방향의 순서도 반시계 방향, 시계 방향으로 달라진다. 공통적으로 방향 전환에 대해서 ..

https://www.acmicpc.net/problem/2503 2503번: 숫자 야구 첫째 줄에는 민혁이가 영수에게 몇 번이나 질문을 했는지를 나타내는 1 이상 100 이하의 자연수 N이 주어진다. 이어지는 N개의 줄에는 각 줄마다 민혁이가 질문한 세 자리 수와 영수가 답한 스트 www.acmicpc.net 풀이 브루트포스, 구현 문제는 개인적으로 너무 어렵다.. 나만의 팁이라고 한다면 dp처럼 공책에다가 써본 후에 로직을 어느 정도 파악하고 코딩을 시작한다. 위 문제의 조건은 아래와 같다. 범위는 세 자릿수 자릿수와 숫자가 같으면 스트라이크 자릿수가 다르고, 숫자가 같은 게 있으면 볼 그럼 이제 문제를 풀어보겠다. [1번 조건] 세 자릿수를 가진 자연수는 100 부터 999 이다. 하지만 중복된 숫..

https://www.acmicpc.net/problem/1034 1034번: 램프 첫째 줄에 N과 M이 주어진다. N은 행의 개수이고, M은 열의 개수이다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 램프의 상태가 주어진다. 1이 켜져있는 상태이고, 0이 꺼져 www.acmicpc.net 풀이 문제를 읽은 직후에 이해가 잘 되지 않았다. 문제 내용은 아래와 같다. 1. 가로 x 세로 크기의 map에 램프가 있다. 2. 각 열의 맨 아래에 해당 열의 램프를 단 번에 키고 끌 수 있는 스위치가 존재한다. 3. 마지막 입력에 스위치를 누를 수 있는 횟수 K가 주어진다. 스위치를 K번 눌러서 각 행의 모든 램프가 켜진 행을 최대한 많이 만들면 된다. 예제 1번을 보면서 문제를 풀어..

https://www.acmicpc.net/problem/1202 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 풀이 이번 문제는 간단한 수학으로 풀 수 있는 문제라고 생각할 수 있지만 보석의 개수와 가방의 무게의 범위가 커서 시간 초과가 발생할 것이다. 시간 초과 에러를 발생시키지 않으려면 우선순위 큐를 이용해야 한다. 우선순위 큐는 여러 개의 값이 들어있을 경우 오름차순으로 자동 정렬된다고 생각하면 된다. 문제 해결 과정은 아래와 같다. 1. ..

https://www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net 풀이 이번 문제는 정렬 후에 간단한 식만 만들어주면 해결할 수 있는 문제다. 각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값을 구하는 문제로 i 번째 사람이 돈을 인출하는데 걸리는 시간은 i-1 번째 사람이 돈을 인출하는데 걸리는 시간 + 이전까지의 대기 시간이다. 이전까지의 대기 시간이 짧을수록 필요한 시간이 줄어들 것이다. 즉, i 번째 사람이 돈을 인출하는데 걸리는 시간이 짧은 순서로 정렬하면 된다. 오름차순 정렬이..