Problem Solving/Baekjoon Online Judge (Platinum) (58) 썸네일형 리스트형 백준 19585 - 전설 (C++) 문제 문제 링크 BOJ 19585 - 전설 문제 요약 $C$가지의 색상과 $N$개의 닉네임이 주어진다. 색상과 닉네임을 순서대로 이어붙여 팀명을 지으면 ICPC 리저널에서 수상할 수 있을 때, $Q$개의 쿼리에 대해 해당 팀이 수상할 수 있는지 여부를 판단해보자. 제한 TL : $3$ sec, ML : $1024$ MB $1 ≤ C, N ≤ 4,000$ $1 ≤ Q ≤ 20,000$ 모든 색상 이름의 길이와 닉네임의 길이는 1,000글자를 넘지 않는다. 각 문자열은 중복되지 않으며 알파벳 소문자로만 이루어져 있다. 알고리즘 분류 자료 구조(data structures) 문자열 (string) 트리 (trees) 트라이 (trie) 해시를 사용한 집합과 맵 (hash _ set / map) 풀이 당연히 무.. 백준 8571 - Apteka (C++) 문제 문제 링크 BOJ 8571 - Apteka 문제 요약 $N$명의 $C_i$값이 주어진다. 자리를 바꿀 때마다 문제에 정의된 데로 비용이 발생할 때, 맨 앞으로 가는 최소 비용을 구해보자. 제한 TL : $1$ sec, ML : $512$ MB $1 ≤ N ≤ 10^6$ $1 ≤ C_i ≤ 10^9$ 알고리즘 분류 다이나믹 프로그래밍(dp) 볼록 껍질을 이용한 최적화 (convex hull trick) 풀이 우선 문제를 다음과 같이 이해하면 편하다. "$Hansel$의 위치가 $0$ 번 인덱스이고, $1, 2, ... N$번 인덱스 사람들의 $C_i$가 주어진다. 자리 스왑마다 $Hansel$과 $i$가 떨어진 거리 * $C_i$ 의 비용이 발생 한다고 할 때 $Hansel$이 $N$번째 자리에 도달.. 이전 1 ··· 5 6 7 8 다음 8/8