김머성 블로그

[BAE/<JOON> 문제풀이] 16367. TV Show Game

https://www.acmicpc.net/problem/16367 16367번: TV Show Game Your program is to read from standard input. The input starts with a line containing two integers, k and n (3 < k ≤ 5,000, 1 ≤ n ≤ 10,000), where k is the number of lamps and n the number of game participants. Each of the following n lines contains t www.acmicpc.net 서론 SCC 단원 마지막 문제였다. 딱히 특별하진 않았던 것 같다. SCC도 그래프다 보니까 직관적이여서 다른 분류들에 비해 좀 ..

[BAE/<JOON> 문제풀이] 1648. 격자판 채우기

https://www.acmicpc.net/problem/1648 1648번: 격자판 채우기 준규는 침대에 누워서 천장을 바라보고 있었다. 천장은 격자판 모양이었고, 계속해서 천장을 바라보다 보니 이런 생각이 들었다. 세로 크기가 N이고, 가로 크기가 M인 격자판을 2x1 크기의 도미노 www.acmicpc.net 서론 컨닝 풀고나니까 같은 문제라는걸 알고 풀었다. 컨닝 풀기 전에는 전혀 생각이 안났다는게 신기하다. 풀이 컨닝과 완전히 같은 문제인 대신 구현이 살짝 더 복잡하다. 격자판을 행으로 구분해 분할하고 각 행마다의 상태를 bitmask를 저장해 중복 계산을 피한다. 로직은 다음과 같다. 1. 현재 행에 빈칸 위치를 계산한다. ( 이전 칸에서 도미노를 세운 위치를 제외한다. ) 2. 각 빈칸마다 ..

[BAE/<JOON> 문제풀이] 1014. 컨닝

https://www.acmicpc.net/problem/1014 1014번: 컨닝 최백준은 서강대학교에서 “컨닝의 기술”이라는 과목을 가르치고 있다. 이 과목은 상당히 까다롭기로 정평이 나있기 때문에, 몇몇 학생들은 시험을 보는 도중에 다른 사람의 답지를 베끼려 한 www.acmicpc.net 서론 번호 순으로 풀 때 초라기에 이어 2번째로 등장하는 보스몹 문제다. 풀이에 비해 티어가 과하게 높게 책정된 것 같다. 기믹이 딱 골드1 스럽다. 그 점 3개 골라서 삼각형 만드는 문제랑 거의 똑같다고 생각한다. 그동안 풀었던 플레 문제중 가장 빨리 풀었다. 문제 독해부터 AC까지 1시간 정도 걸린것 같다. (OUO) V 풀이 k번째 행의 배치를 정해놓고 최종적으로 n행까지 진행했을 때 정해지는 최대 학생 수..

[BAE/<JOON> 문제풀이] 12287. 해밀턴 경로

https://www.acmicpc.net/problem/12287 12287번: 해밀턴 경로 N개의 정점과 N(N-1)/2개의 간선으로 이루어진 방향 그래프 G가 있다. 정점은 0부터 N-1까지 번호가 매겨져 있다. 서로 다른 두 정점 (i, j) 사이에는 i에서 j로 가는 간선 또는 j에서 i로 가는 간선이 www.acmicpc.net 서론 발상 못 떠올려서 검색해보다가 이 문제에 대한 논문이 있다는걸 알았다. ㄷㄷ.. 나름 유명한 문제인 것 같다. https://imada.sdu.dk/u/jbj/DM19/turnering.pdf 풀이 발상 실패 후 BF부터 시도해봤다. 당연히 2^n 보다 빠른 알고리즘을 작성할 수 없다. n=100이다. 아래는 검색한 내용을 바탕으로 작성한 풀이다. 이 문제의 핵심..

[BAE/<JOON> 문제풀이] 19623. 회의실 배정 4

https://www.acmicpc.net/problem/19623 19623번: 회의실 배정 4 서준이는 아빠로부터 N개의 회의와 하나의 회의실을 선물로 받았다. 각 회의는 시작 시간, 끝나는 시간, 회의 인원이 주어지고 한 회의실에서 동시에 두 개 이상의 회의가 진행될 수 없다. 단, www.acmicpc.net 서론 라인 스윕 DP 풀이 회의 구간이 겹치지 않으면서 가장 많은 인원을 회의에 참석시켜야 하므로 겹치기 여부 판정은 라인 스윕으로, 인원수 최대화는 DP로 나눠 생각할 수 있다. 첫번째, DP 점화식은 아래와 같다. DP[i] = i번째 회의까지 참여시킬 수 있는 최대 인원 수 DP[i] = max(i번째 이전의 i번째 회의와 겹치지 않고 함께 진행할 수 있는 회의 인원수 총합 + i번째 ..

[BAE/<JOON> 문제풀이] 20928. 걷는 건 귀찮아

https://www.acmicpc.net/problem/20928 20928번: 걷는 건 귀찮아 일직선 위에 놓인 $N$개의 지점 $p_i$에는 최대 $x_i$만큼 이동시켜주는 인력거꾼들이 있다. 즉, $p_i$에 있는 인력거꾼은 $p_i$, $p_i+1$, $p_i+2$, $...$, $p_i+x_i$ 중 한 지점까지 승객을 데려다준다. 세상 www.acmicpc.net 서론 라인 스윞 기본 문제 ( 그리디 ) 풀이 어떤 인력거의 출발 도착 위치가 s, e이고 모든 인력거들이 출발점을 기준으로 정렬되어 있다면, 이 인력거로 갈아탈 수 있는 이전 인력거는 출발점이 e보다 작아야 한다. 조건을 만족하는 인력거들을 찾아가며 환승 횟수를 갱신해 답을 구할 수 있다. 그리고 풀이를 쓰면서 생각난건데, 검사한 ..