Always awake

03/20 DP https://boj.kr/2293 동전 1 (G5) 이제 DP연습해야지.. 처음에는 DP[N][K]로 각 동전마다 돌면서 가지수를 구해줬다. $DP_{ij} = \sum_{k=0} ^{j // i} DP_{i-1j-k*coin}$ 근데 메모리 초과가 나더라?!! 생각해보니 어차피 i-1번째만 참고해서, 한줄로 가능하다! 그리고 여러번 업데이트되는쪽은 자기의 j-coin번째만 참고하면 된다. 따라서 $DP_i = DP_i-coin$을 $i*j$번 돌면 완료! https://boj.kr/2294 동전 2 (G4) 위 문제와 같은 상황이지만, 이번에는 그걸 만족하는 최소 동전수 구하기 비슷한 방법으로 채우면 되지 않을까? 음! 잘 된다. 거의 같은 아이디어네. https://boj.kr/18..

3/13 이분 매칭으로 룩 / 나이트의 움직임의 최대 매칭을 계산할 수 있는데, 시도해보자! 그래프 이분 매칭 https://boj.kr/1017 소수 쌍 (P3) 소수 쌍 이분매칭으로 구하기.. 미리 한개 고정해놓고 하는 느낌? 얘는 구현 하면 그냥 바로 되네 https://boj.kr/9525 룩 배치하기 (P3) 룩의 움직임은 결국 가로먹기 + 세로먹기의 이분 매칭이다.. 미친 풀이.. 진짜 개똑똑하다 사람들. 구현을 어떻게 할지가 고민되긴 하네.. 깔끔하게 쪼개려고하면 조금 신경쓸게 있었지만, 그냥 앞끝 / 뒤끝만 신경면서 가로로 순회한번, 세로로 순회한번 돌면 처리되는 영역이었다. 근데 그거조차 귀찮아서 그냥 다음줄 넘어갈때 / X 만날때 번호 1씩 계속 늘려줘서, 최대 MX는 5000에서 10..

투 포인터 S, E 혹은 L, R이라는 두가지 변수를 지정하여, 인덱싱을 저장하고자 한다. (두 포인터) 이후 각 포인터들을 이용하여 목표를 달성하자. 문제의 경우는 [3, 7, 2, 1, 6, 9, 11, 14] 라는 배열에서 합이 9인 연속된 부분을 찾는것 S, E 포인터 모두 인덱스 0번에서 시작하여 현재 합이 9보다 작다면 E를 한칸 오른쪽으로, 크다면 S를 한칸 오른쪽으로 이동하며 값을 구한다. 여러가지 방면에서 활용할 수 있으며, 이때 E-S가 일정하다면 슬라이딩 윈도우 라고 한다. 슬라이딩 윈도우 투 포인터 와 비슷하지만, 두 포인터 사이 간격이 일정해서 마치 유리창을 미닫는 모양이라고 하여 슬라이딩 윈도우라고 불리는 알고리즘 위 그림은 N = 8인 배열에서 K = 3의 길이를 가지는 부분수..

문제 A 씨는 어떤 회사 빌딩의 수위로 일하고 있다. A 씨는 밤 12 시가 되면 이 빌딩 사무실의 켜져 있는 모든 등과 건물 옥상에 있는 전광판을 소등한 후 퇴근한다. 그런데 이 빌딩은 특이한 구조로 이루어져 있다. 각 층에는 동일한 개수의 사무실이 일렬로 늘어서 있고, 건물 양편에 엘리베이터가 있다. 왼쪽에 있는 엘리베이터는 올라갈 때만 탈 수 있는 엘리베이터이고 오른쪽에 있는 엘리베이터는 내려갈 때만 탈 수 있는 엘리베이터이다. 전광판을 끄기 전에는 왼쪽에 있는 엘리베이터만 탈 수 있고, 끈 이후에는 오른쪽에 있는 엘리베이터만 탈 수 있다. 사무실 등은 왼쪽 엘리베이터를 타고 올라가면서 들러 소등할 수도 있고, 오른쪽 엘리베이터를 타고 내려오면서 들러 소등할 수도 있다. A 씨는 왼쪽 엘리베이터 1..

문제 전구 100개가 10×10 정사각형 모양으로 늘어서 있다. 전구에 달린 스위치를 누르면 그 전구와 위, 아래, 왼쪽, 오른쪽에 있는 전구의 상태도 바뀐다. 전구 100개의 상태가 주어지면 모든 전구를 끄기 위해 최소한으로 눌러야 하는 스위치의 개수를 출력하라 입력 10줄에 10글자씩 입력이 주어진다. #은 꺼진 전구고 O(대문자 알파벳 o)는 켜진 전구다. #과 O외에는 입력으로 주어지지 않는다. 출력 모든 전구를 끄기 위해 최소한으로 눌러야 하는 스위치의 개수를 출력하라. 불가능하면 -1를 출력하라. 테스트케이스 #O######## OOO####### #O######## ####OO#### ###O##O### ####OO#### ########## ########O# #######OOO #####..

문제 철수와 민수는 카드 게임을 즐겨한다. 이 카드 게임의 규칙은 다음과 같다. N개의 빨간색 카드가 있다. 각각의 카드는 순서대로 1부터 N까지 번호가 매겨져 있다. 이 중에서 M개의 카드를 고른다. N개의 파란색 카드가 있다. 각각의 카드는 순서대로 1부터 N까지 번호가 매겨져 있다. 이 중에서 빨간색에서 고른 번호와 같은 파란색 카드 M개를 고른다. 철수는 빨간색 카드를 가지고 민수는 파란색 카드를 가진다. 철수와 민수는 고른 카드 중에 1장을 뒤집어진 상태로 낸다. 그리고 카드를 다시 뒤집어서 번호가 큰 사람이 이긴다. 이 동작을 K번 해서 더 많이 이긴 사람이 최종적으로 승리한다. 한 번 낸 카드는 반드시 버려야 한다. 철수는 뛰어난 마술사이기 때문에 본인이 낼 카드를 마음대로 조작할 수 있다...

문제 낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다. 칸에는 상어가 최대 한 마리 들어있을 수 있다. 상어는 크기와 속도를 가지고 있다. 낚시왕은 처음에 1번 열의 한 칸 왼쪽에 있다. 다음은 1초 동안 일어나는 일이며, 아래 적힌 순서대로 일어난다. 낚시왕은 가장 오른쪽 열의 오른쪽 칸에 이동하면 이동을 멈춘다. 낚시왕이 오른쪽으로 한 칸 이동한다. 낚시왕이 있는 열에 있는 상어 중에서 땅과 제일 가까운 상어를 잡는다. 상어를 잡으면 격자판에서 잡은 상어가 사라진다. 상어가 이동한다. 상어는 입력으로 주어진 속도로 이동하고, 속도의 단위는..

문제 때는 2040년, 이민혁은 우주에 자신만의 왕국을 만들었다. 왕국은 N개의 행성으로 이루어져 있다. 민혁이는 이 행성을 효율적으로 지배하기 위해서 행성을 연결하는 터널을 만들려고 한다. 행성은 3차원 좌표위의 한 점으로 생각하면 된다. 두 행성 A(xA, yA, zA)와 B(xB, yB, zB)를 터널로 연결할 때 드는 비용은 min(|xA-xB|, |yA-yB|, |zA-zB|)이다. 민혁이는 터널을 총 N-1개 건설해서 모든 행성이 서로 연결되게 하려고 한다. 이때, 모든 행성을 터널로 연결하는데 필요한 최소 비용을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -109..