Hello, Freakin world!

https://www.acmicpc.net/problem/1052 1052번: 물병 지민이는 N개의 물병을 가지고 있다. 각 물병에는 물을 무한대로 부을 수 있다. 처음에 모든 물병에는 물이 1리터씩 들어있다. 지민이는 이 물병을 또 다른 장소로 옮기려고 한다. 지민이는 한 번 www.acmicpc.net 풀이 방법 이 풀이 방법은 아주 직관적이고 쉽습니다. 1. 1L 물병의 개수가 2의 제곱수인 경우, 하나의 물병에 옮길 수 있다는 점을 이용해, N을 2의 제곱수로 분해한다. (이때 분해된 개수가 물병의 개수다.) 2. 물병의 개수가 K보다 크다면 크기가 작은 물병들부터 합쳐나간다. 예를 들어, N = 11인 경우 8, 2, 1로 분해할 수 있겠죠. 이는 세 개의 물병에 각각 8L, 2L, 1L가 들어..

www.acmicpc.net/problem/15684 15684번: 사다리 조작 사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선 www.acmicpc.net 풀이 아이디어 놓을 수 있는 사다리 위치에 사다리를 하나씩 놓아보고 그때마다 사다리 게임을 돌려 확인하는 방식으로 풀 수 있습니다. 사실 말이 쉽지, 꽤 까다로웠습니다. 구현 문제는 정말 너무 어려운 것 같네요. 가중 중요하게 신경써야될 한 가지 포인트만 소개하겠습니다. putLadderDown의 재귀 방식 putLadderDown 메서드 안에는 이중 for문이 있습니다. 놓을 수 있는 위치에 사다리를 놓고,..

www.acmicpc.net/problem/16551655번: 가운데를 말해요첫째 줄에는 수빈이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 수빈이가 외치는 정수가 차례대로 주어진다. 정수는 -1www.acmicpc.net 단순하게 접근하기문제에서 N개의 다양한 크기의 정수가 주어집니다.이 정수들이 하나씩 주어질 때마다 이전까지의 값들을 고려한 중간값을 찾아내야 합니다.가장 단순한 접근은 값들을 리스트에 넣고 값이 주어질 때마다 리스트를 복사해 정렬한 뒤 중간값을 찾아내는 것입니다.이럴 경우 리스트 복사 비용을 제외하더라도 시간 복잡도는 O(N^2 * logN)이 되기 때문에 시간초과로 실패합니다.(N 3이므로 3이 최..

www.acmicpc.net/problem/3055 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net BFS 방식을 사용해 최단 거리를 찾는 문제입니다. 포인트는 두 가지입니다. 1. 노드를 큐에 넣을 때, 물에 잠기는 장소인지 검사할 것 2. BFS의 깊이가 깊어질 때마다 잠기는 부분이 확산되도록 구현 1번은 해당 지역 상하좌우로 물이 있는지 검사하면 됩니다. 2번은 큐에서 꺼내져 나오는 노드의 depth가 깊어질때마 수행해줍니다. 둘 다 그리 어려운 구현은 아니라 딱히 할말은 없지만, 코드를 정리하지 않으면서 구현하면 ..

www.acmicpc.net/problem/17144 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net 구현 문제입니다. 중요한 구현 포인트는 두 가지입니다. 1. 미세먼지 확산 2. 바람 방향으로 먼지 이동시키기 1번은 그리 어렵지 않습니다. 동시에 모두 확산해야하므로 임시 배열 하나를 생성해 확산 결과를 통합해주고, 원래 배열에 덮어쓰면 해결 2번은 어떻게 구현하느냐에 따라 꽤 헤깔릴 수 있습니다. 변수 설정하고 값 저장했다가 다시 옮기고... 이런 과정들이 너무 짜증나서 저는 경로를 쭉 따라가 deque에..

www.acmicpc.net/problem/15685 15685번: 드래곤 커브 첫째 줄에 드래곤 커브의 개수 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 드래곤 커브의 정보가 주어진다. 드래곤 커브의 정보는 네 정수 x, y, d, g로 이루어져 있다. x와 y는 드래곤 커 www.acmicpc.net 풀면서 화딱지가 나서 때려칠까 몇번이나 고민했었던 문제였네요. 바로 본론으로 들어가서, 포인트는 한 점을 중심으로 어떤 점을 90도 이동시키는 함수를 만드는 일입니다. 드래곤 커브 특성상, 새로운 세대를 만들때 끝점을 중심으로 그 이전 점들을 하나씩 90도 이동시킵니다. 리스트로 구현하려면 리스트의 마지막이 끝점이 됩니다. 끝점의 참조를 저장해두고 역순으로 리스트를 순회하며 90도 회..

www.acmicpc.net/problem/1662 1662번: 압축 압축되지 않은 문자열 S가 주어졌을 때, 이 문자열중 어떤 부분 문자열은 K(Q)와 같이 압축 할 수 있다. K는 한자리 정수이고, Q는 0자리 이상의 문자열이다. 이 Q라는 문자열이 K번 반복된다는 뜻이 www.acmicpc.net 포인트 유효한 괄호 단위로 문자열을 잘라 재귀로 넘기는게 포인트입니다. 여는 괄호가 나오면 이 여는 괄호의 짝인 닫는 괄호를 찾아줘야 됩니다. 그리고 그 문자열을 잘라 재귀로 넘겨주면서 글자 수를 계산하면 됩니다. 짝인 닫는 괄호를 구하는 방법은 간단합니다. 문자열을 순회하면서 openBracketCount(여는 괄호 수)를 세고 있다가 닫는 괄호가 나오면 하나씩 openBracketCount-1 해줍니다..

www.acmicpc.net/problem/14719 14719번: 빗물 첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500) 두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치 www.acmicpc.net 해결 방법 물을 가두는데 leftWall, rightWall가 필요하다고 합시다. leftWall에 임의의 높이가 정해졌다고 할때, rightWall의 높이가 이보다 크거나 같을 경우에만 그 사이 담긴 물의 양을 계산합니다. 그리고 이걸 정방향, 역방향으로 둘다 해줍니다. ... public class Main { static int H,N; public static void main(Stri..

www.acmicpc.net/problem/2304 2304번: 창고 다각형 첫 줄에는 기둥의 개수를 나타내는 정수 N이 주어진다. N은 1 이상 1,000 이하이다. 그 다음 N 개의 줄에는 각 줄에 각 기둥의 왼쪽 면의 위치를 나타내는 정수 L과 높이를 나타내는 정수 H가 한 개의 www.acmicpc.net 오랜만이라서 그런지 절대 쉽지 않았습니다... 꽤 오래 걸렸네요. 핵심은 기둥이 높아질 때마다 지붕 높이를 갱신하고 넓이를 추가해준다는 점. 그리고 동일한 방법을 정방향, 역방향으로 수행하면서 전체 넓이를 계산하는 겁니다. 처음에 한 방향으로만 풀려고하니 복잡도가 확 올라가 버리더군요. 그리고 주의할 점은 정방향으로 쭉 가서 계산하면서 마지막 가장 높은 기둥의 위치를 저장해두고 그 지점까지만 역..

www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net 쉬울 줄 알고 덤볐다가 꽤 시간을 잡아 먹은 문제입니다. 문제를 살펴보면 해야될 작업이 딱 두 가지가 떠오를 겁니다. 1. 쪼개지는 빙산의 개수 구하기 2. 배열을 순회하면서 얼음 녹이기 1번은 전형적인 그래프 컴포넌트 개수 구하기 문제입니다. 2번은 하나의 좌표가 주어질 때, 상하좌우에 0이 있는 개수만큼 값을 빼주면 되고요. 저는 1,2번 작업을 분리시켜서 구현했었는데, 시간 초과가 발생했습니다. 그래..