BOJ 20047 - 동전 옮기기
문제 문자열의 길이 n, 문자 o, x로 이루어진 문자열 S, T, 이동시킬 문자의 위치 i, j가 주어진다. 문자열 S에서 i, j 위치에 있는 문자 두 개의 위상을 유지하면서 이동시켜 T로 변환할 수 있는지 판별하는 문제이다. 이때 i, j는 [0, n)의 범위로 주어진다. ...
Recent posts
BOJ 22871 - 징검다리 건너기 (large)
문제 수열 \(A_N=A_1A_2\dots{A_i}\dots{A_N}\)에 대해 항 사이를 이동할 수 있다. 항상 오른쪽으로만 이동 가능하고, \(i\) 번째 항에서 \(j\) 번째 항으로 이동할 때 드는 비용은 \((j-i)\times{(1+|A_i-A_j|)},\quad i&...
BOJ 21606 - 아침 산책
문제 모든 점이 1(실내), 0(실외)로 구분되는 트리가 주어졌을 때, 산책할 수 있는 경로의 개수를 구하는 문제이다. 경로의 조건은 처음과 끝 지점이 1(실내)이어야 하며, 이외의 점들은 모두 0(실외)여야 한다는 것 뿐이다. 따라서 경로 \(P\)를 뒤집은 경로도 $$P$와 ...
BOJ 17270 - 연예인은 힘들어
문제 그래프 상의 두 점 \(v_j, v_s\)가 주어지면, 임의의 점 \(v\)에 대해 두 점과의 최단 경로의 합이 최소가 되는 점들을 찾고, 나머지 쿼리들을 적용시키는 문제이다. 조건 1. 지헌이의 출발 위치와 성하의 출발 위치는 새로운 약속 장소가 될 수 없다. 조건 2....
BOJ 1135 - 뉴스 전하기
문제 임의의 트리가 주어지고 한 노드는 1분에 하나의 자식에게 전화할 수 있을 때, 루트에서 시작해 모든 노드가 전화를 받기까지 몇 분이 걸리는지 계산하는 문제이다. 풀이 한 노드에 대해, 자식 노드 각각을 루트로하는 서브 트리의 소요 시간이 많은 자식부터 전화를 해야 하기 ...