본문 바로가기

PS4

CSES PS - Towers (그리디, sorting) https://cses.fi/problemset/task/1073 sorting and searching으로 분류된 것으로 볼때, 무작위 크기를 순서대로 multiset에 넣으면서 처리하는 것에 주목하라는 의미인 듯 하다. 큐브를 이용해서 타워를 쌓을 것이다. (큰 큐브 위에 작은 큐브를 올리거나, 새로운 타워의 기반으로 사용하거나) n개의 큐브의 크기가 주어질 때, 모든 큐브를 사용해서 만들 수 있는 타워의 최소개수를 구해라. (반드시 입력 순서대로 처리해야 한다.) i번째 큐브를 이용해서 타워를 쌓을 땐, 그보다 약간 큰 큐브 위에 두는 게 최적이다. int main() { FAST; int n; cin >> n; multiset st; while (n--) { int a; cin >> a; auto.. 2020. 1. 13.
BOJ 15590 - Rental Service (usaco silver, 그리디, 구간합배열, 이분탐색) https://www.acmicpc.net/problem/15590 그리디 + 이분탐색 + 구간합배열로 풀었다. 생각한 순서는 1. 모든 소 N마리에 대해 i번쨰 소를 우유를 팔거나, 빌려주거나 하는 완탐 -> (O(2^1000000) 시간초과 2. 소의 우유 산출량을 내림차순 정렬한 후, 0~i번째 소는 우유를 팔기로 한다면, i+1~n-1번쨰 소는 반드시 빌려줘야 한다. 빌려주는 경우는 간단하게 처음부터 더해주면 되기 떄문에 그에 맞는 구간합배열을 저장해 뒀다면 상수시간에 도출할 수 있다. 문제는 0~i번째 소의 우유를 팔때의 수익을 반환하는 함수의 논리이다. 그냥 앞에서부터 긁어주면 O(i)로 할 수 있는데, 이렇게 되면 시간 초과가 난다. (p,q)를 q에 대해서 내림차순으로 정렬한다면, 다음과 .. 2019. 10. 11.
BOJ 1194 - 달이 차오른다, 가자 https://www.acmicpc.net/problem/1194 1194번: 달이 차오른다, 가자. 첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 50) 둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고, 영식이가 열쇠를 숨겨놓는 다면 문에 대응하는 열쇠가 없을 수도 있다. 0은 한 개, 1은 적어도 한 개 있다. 그리고, 열쇠는 여러 번 사용할 수 있다. www.acmicpc.net 제약조건(열쇠,문)이 추가된 플러드필 문제이다 처음엔 큐에 방문노드위치(cy,cx)와 비트마스크를 이용한 현재 key, 그리고 visited배열을 넘겨주면서 열쇠를 먹으면 false로 초기화된 visited를 다음 .. 2019. 8. 6.
BOJ 2098 - 외판원 순회 TSP https://www.acmicpc.net/problem/2098 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j로 가기 위한 비용을 나타낸다. 항상 순회할 수 있는 경우만 입력으로 주어진다. www.acmicpc.net #include #include #include using namespace std; const int INF = 1e9; int n, w[16][16], dp[16][1 2019. 8. 6.

티스토리툴바