프로그래밍/PS (6) 썸네일형 리스트형 [백준/BaekJoon] 15591 - "MooTube (Silver)" C++ 풀이 문제 요약그래프가 주어지고 특정 노드에서 다른 노드로 가는 모든 거리 비용이 특정 비용 $K$를 넘어가는 경우의 수를 구하는 문제 사용 알고리즘그래프 이론그래프 탐색너비 우선 탐색 (BFS)깊이 우선 탐색 (DFS) 도 가능 문제 해설처음에는 플로이드 워셜 알고리즘으로 모든 간선의 최단 거리 비용을 계산하면 되겠다 싶었지만, 문제는 추가적으로 간선이 생성되는 것이 아니라 원래 있던 간선을 이용해서 비용만 구하는 것이다. 따라서 직접 탐색을 통해 구해야 된다...비용을 미리 다 구해놓고 비교하는 방식도 있겠지만 가장 효율적인 것은 입력 받은 $v_i$ 부터 갈 수 있는 노드를 탐색하면서 $K$이상인 노드가 나올 경우에만 `count`를 증가시켜주면 된다. 낮은 경우의 간선은 어짜피 해당하는 노드들은 전부 .. [백준/BaekJoon] 16236 - "아기 상어" C++ 풀이 문제 요약아기 상어가 자신의 크기보다 작은 물고기를 최단 경로로 먹으러 다니며 최대한 많이 먹었을 때의 시간(광고 게임 생각나는건 기분탓...) 사용 알고리즘구현시뮬레이션너비 우선 탐색 (BFS)우선순위 큐 문제 해설사실 상 구현이 대부분이라 시간이 오래 걸리는 문제. 우선 순위 기준에 맞춰 매 횟수마다 BFS를 돌려 작은 물고기들을 먹으러 다니면 되는 문제이다. BFS로 최단 경로에 있는 물고기들의 후보를 구하고 저장하는데, 우선 순위 큐를 이용하여 가장 왼쪽 위 물고기가 선택될 수 있게 pq를 사용하였다. 거의 다 풀어놓고 2%에서 계속 시간 초과가 뜨는 이슈를 겪었는데, 찾아보니 무한 루프에 빠진 것이라고 한다... 아기 상어를 표현하는 숫자가 9인데, 아기 상어의 크기가 10이 되었을 때 문제가 .. [백준/BaekJoon] 13904 - "과제" C++ 풀이 https://www.acmicpc.net/problem/13904 문제 이름만 들어도 무시무시 하다.문제 요약여러가지 과제가 있고, 이 과제마다 마감일과 점수가 있다. 점수의 최댓값을 구하는 문제. 사용 알고리즘자료 구조그리디 알고리즘우선순위 큐 문제 해설생각보다 다양한 풀이법이 존재했는데, 나같은 경우에는 일자를 거꾸로 돌면서 할 수 있는 과제중 최고점인 과제를 우선순위 큐에서 뽑아와 더하는 식으로 풀이를 하였다. 문제 코드#include using namespace std;int main(){ ios_base::sync_with_stdio(0); cin.tie(0); priority_queue pq; vector> arr(1001); int N; cin >> N; .. [백준/BaekJoon] 32143 - "카드 게임 (Hard)" C++ 풀이 https://www.acmicpc.net/problem/32143문제 요약적의 체력인 $H$를 손에 있는 카드의 $D$ 공격력 만큼 깎을 수 있는데 최소 카드 사용 횟수를 구하는 문제. $Q$번 횟수 만큼 추가되는 카드마다 다시 최소 카드 사용 횟수를 재계산해야 한다. 사용 알고리즘자료 구조그리디 알고리즘우선순위 큐 문제 해설우선순위 큐를 사용하여 `pq.size()`를 출력해주면 되는 아주아주 간단한 문제였다... 나는 처음에 직접 count를 해서 구할려고 하다 보니 시간 초과와 길어진 코드 때문에 시간을 날렸었다... 아이디어는 우선순위 큐를 오름차순으로 정렬하여 우선순위 큐의 합이 H보다 이상인 조건을 만족하는 만큼만 작은 수를 빼서 관리하는 식이다. 문제 코드#includeusing names.. [NYPC 2024_본선] 1214부문 - 마법의 룬 패턴 찾기 풀이 공유 https://nypc.github.io/2024/final_2 NYPC 2024 넥슨 청소년 프로그래밍 챌린지NEXON YOUTH PROGRAMMING CHALLENGE, 세상을 바꾸는 코딩! 세상을 더 멋지게 바꿀 당신을 만나고 싶습니다.www.nypc.co.krhttps://www.biko.kr/problem/4899 무료 프로그래밍 학습 플랫폼 BIKO코딩의 기초부터 심화까지 단계별로 공부해 보세요!www.biko.kr 본선 문제 중에서 가장 쉬웠던 문제입니다. 아래 해설을 참고하면 다음과 같습니다.답은 항상 $T$ 또는 $T′$ 의 첫 몇 글자(접두사)이다. 따라서 $T$ 또는 $T′$ 의 길이가 $K, K−1, ⋯,1$인 접두사만 확인하면 되고, $P$의 후보가 주어졌을 때 $P$와 $P′$.. [NYPC 2024_본선] 1214부문 - 훈련 프로그램 1 풀이 공유 https://nypc.github.io/2024/final_4 NYPC 2024 넥슨 청소년 프로그래밍 챌린지NEXON YOUTH PROGRAMMING CHALLENGE, 세상을 바꾸는 코딩! 세상을 더 멋지게 바꿀 당신을 만나고 싶습니다.www.nypc.co.kr https://www.biko.kr/problem/4901 무료 프로그래밍 학습 플랫폼 BIKO코딩의 기초부터 심화까지 단계별로 공부해 보세요!www.biko.kr최근에 나온 문제여서 그런지 풀이 방법이 검색이 안됐습니다. 넥슨 코테를 준비하면서 풀어보려고 했는데 풀이 방법이 어려워서 AI한테 물어봐서 겨우겨우 풀었습니다. 문제에 기본 접근은 동적계획법(Dynamic Programming, DP)이고, 추가로 장난질을 좀 더 해야 만점을 받.. 이전 1 다음
