Programmers - 사라지는 발판(Java)
https://programmers.co.kr/learn/courses/30/lessons/92345 코딩테스트 연습 - 사라지는 발판 [[1, 1, 1], [1, 1, 1], [1, 1, 1]] [1, 0] [1, 2] 5 [[1, 1, 1], [1, 0, 1], [1, 1, 1]] [1, 0] [1, 2] 4 programmers.co.kr 풀이 다음 2가지의 경우에 승패가 결정됨 상하좌우 4방향 중 어떠한 방향으로도 이동 불가인 경우 하나의 발판에 2명이 위치할 때, 한명이 다른 발판으로 이동하여 현재 발판이 사라질 때 지는 플레이어든 이기는 플레이어든 각자 최적의 플레이로 진행 이기는 플레이어 - 최대한 빨리 승리하는 방향으로 진행 -> 움직이는 횟수를 최소화 지는 플레이어 - 최대한 오래 버티는..
2022. 2. 3.
BOJ 1202 - 보석 도둑(Java)
https://www.acmicpc.net/problem/1202 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 풀이 완전 탐색으로 풀 경우 보석의 개수 N(1 ~ 300,000), 가방의 개수 M(0 ~ 100,000,000)으로 O(N*M)의 시간 복잡도를 가짐, 안될 거라 생각하고 풀어봤지만 역시나 시간초과 발생 * 시간 복잡도를 줄여야하며 우선순위 큐를 이용하여 품 우선 순위 큐를 이용한 풀이 - 가방에 대해서는 for문을 이용하여 탐색 -..
2021. 12. 31.
