봉황대 in CS

백준 2224번을 풀며 플로이드-와샬 알고리즘을 사용할 때 주의해야 할 점을 깨닫게 되었고, 이를 잊지 않기 위해서 이렇게 글로 남긴다. 플로이드-와샬 알고리즘 이 알고리즘이 무엇인지에 대해서는 이전에 작성한 글을 참고하길 바란다. [알고리즘] 플로이드-와샬(Floyd-Warshall) 알고리즘 플로이드-와샬(Floyd-Warshall) 알고리즘 '거쳐가는 정점'을 기준으로 모든 정점에서 모든 정점으로의 최단 경로를 구하는 알고리즘이다. ( ↔︎ 다익스트라 : 하나의 정점에서 출발했을 때 다른 모 eunajung01.tistory.com 문제 2224번: 명제 증명 첫째 줄에 출력할 명제의 개수 X개를 출력한다. 다음 X개의 줄에 증명될 수 있는 명제를 한 줄에 하나씩 출력한다. 명제를 출력할 때에는 전..

문제 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 1부터 n까지 번호가 붙어 있는 n개의 포도주가 들어있는 잔이 일렬로 놓여있다. 포도주 시식에는 두 가지 규칙이 존재한다. 1. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다. 2. 연속으로 놓여 있는 3잔을 모두 마실 수는 없다. 각 포도주 잔에 들어있는 포도주의 양이 주어졌을 때, 최대로 마실 수 있는 포도주의 양을 구하는 것이 문제이다. 풀이 DP로 문제를 해결할 수 있다. 첫번째 시도 (..

문제 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 2행 n열로 배치되어 있는 스티커 뭉탱이가 있다. 스티커의 품질은 좋지 않아서, 스티커 한 장을 떼면 그 스티커와 변을 공유하는 스티커는 모두 찢어져서 사용할 수 없게 된다. (뗀 스티커의 왼쪽, 오른쪽, 위, 아래에 있는 스티커는 사용할 수 없게 됨) 모든 스티커를 붙일 수 없으니, 각 스티커에 점수를 매겨 점수의 합이 최대가 되도록 스티커를 떼어내려고 한다. 즉, 2n개의 스티커 중 점수의 합이 최대가 되면서 서로 변을 공유하지 않는 스티커 ..

문제 13164번: 행복 유치원 행복 유치원 원장인 태양이는 어느 날 N명의 원생들을 키 순서대로 일렬로 줄 세우고, 총 K개의 조로 나누려고 한다. 각 조에는 원생이 적어도 한 명 있어야 하며, 같은 조에 속한 원생들은 서로 www.acmicpc.net 행복 유치원에는 N명의 원생들이 있다. (1 ≤ N ≤ 300,000) - 30만명이 있는 유치원 ㄷㄷ 이들을 키에 대하여 오름차순으로 일렬로 세운 후 총 K개의 조로 나누려고 한다. 각 조에는 원생이 적어도 한 명 있어야 하며, 같은 조에 속한 원생들은 서로 인접해 있어야 한다. 조별로 인원수가 같을 필요는 없다. 이렇게 나눠진 조 각자 단체 티셔츠를 맞추려고 한다. 조마다 티셔츠를 맞추는 비용은 조에서 가장 키가 큰 원생과 가장 키가 작은 원생의 키..

문제 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net N×M×H 크기의 상자에 토마토들이 보관된다. (1칸 1토마토) (입력으로 주어지는 값) 1 : 익은 토마토 / 0 : 익지 않은 토마토 / -1 : 토마토가 들어있지 않음 보관 후 하루가 지나면 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 인접한 곳 : 위, 아래, 왼쪽, 오른쪽, 앞, 뒤 (총 6 방향) 창고에 보관된 토마토가 모두 익을 때까지 최소 며칠이 걸리는지를 계산 구하는 ..

문제 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net N×N 공간에 물고기 M마리와 아기 상어 1마리가 있다. 처음에 아기 상어의 크기는 2, 1초에 상하좌우로 인접한 한 칸씩 이동한다. 아기 상어는 자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없다. 자신의 크기보다 작은 물고기만 먹을 수 있기에, 크기가 같은 물고기는 먹을 수 없고 지나갈 수는 있다. 아기 상어는 자신의 크기와 같은 수의 물고리를 먹을 때마다 크기가 1 증가한다. 아기 상어가 어디로 이동할지 결정하는 방법은 아래와 같다. 1. 더..

문제 20056번: 마법사 상어와 파이어볼 첫째 줄에 N, M, K가 주어진다. 둘째 줄부터 M개의 줄에 파이어볼의 정보가 한 줄에 하나씩 주어진다. 파이어볼의 정보는 다섯 정수 ri, ci, mi, si, di로 이루어져 있다. 서로 다른 두 파이어볼의 위치 www.acmicpc.net 마법사 상어는 N×N 격자(1번~N번)에 파이어볼 M개를 발사한다. 격자의 행과 열 각각은 1번과 N번이 연결되어 있다. 파이어볼은 각각 위치(r행 c열), 질랑 m, 방향 d, 속력 s의 정보를 가지며, 해당 위치에서 대기하고 있다. 마법사 상어가 모든 파이어볼에게 K번의 이동을 명령한다. 파이어볼은 자신의 방향으로 속력 s칸만큼 이동하는데, 방향은 다음의 8개 칸의 방향을 의미한다. 파이어볼이 한번 이동을 할 때마다..

문제 17140번: 이차원 배열과 연산 첫째 줄에 r, c, k가 주어진다. (1 ≤ r, c, k ≤ 100) 둘째 줄부터 3개의 줄에 배열 A에 들어있는 수가 주어진다. 배열 A에 들어있는 수는 100보다 작거나 같은 자연수이다. www.acmicpc.net 크기가 3×3인 배열 A가 있으며, 배열의 인덱스는 1부터 시작한다. 1초가 지날 때마다 배열에 다음 두 개의 연산 중 하나가 적용된다. 1. R 연산 : 행의 개수 ≥ 열의 개수인 경우, 배열 A의 모든 행에 대하여 정렬을 수행 2. C 연산 : 행의 개수 r and len(A[0]) > c: # 범위 확인 (런타임 에러 - Index error 발생) if A[r][c] == k: break if time == 100: time = -1 br..