반응형 오블완3 [SWEA/C++] DAG 동전 게임 문제 문제 설명 ">문제 문제 설명 풀이 ">풀이 [문제 풀이] 이 문제는 설명을 잘 이해해야 쉽게 풀 수 있는 문제다. 먼저 조건을 보면 사이클이 있으며 위상 정렬이 되어있다.이를 이용하면 DFS로 1번 노드부터 시작해 N번노드와 N-1번 노드에 도착하는 경우에 돈을 얼마 미만 갖고 있어야 하는지 파악 할 수 있다. 먼저 그림을 통해 예를 들어 보자. 위 그림과 같은 경우에는 N-1과 N으로 바로 가는 방법이 있다.그러므로 다현의 돈의 비율이 나연의 비율과 같은 1:1 미만이면 무조건 나연이 승리한다는 사실을 알 수 있다. 이번에는 조금 다른 경우를 그려보자 위 그림을 보면 N-1과 직접 연결된 경로가 있으면 가진 돈을 전부 제시해 N-1로 가도록 유도할 수 있.. 2024. 11. 26. [백준/C++] ChatGPT 만들기 (No. 31911) 문제 문제 설명 ">문제 문제 설명 풀이 ">풀이 [문제 풀이] 이 문제는 구현만 잘하면 되는 문제다. 각 문자별로 다음에 어떤 문자가 올지 정해지면 이를 이용해 사이클을 찾아 계산하면 된다. 먼저 크게 두가지 경우로 나눌 수 있다. 1. 문자를 반복하면 ']' 로 끝나는 경우2. 문자를 반복하면 계속 사이클이 생성되는 경우 1번의 경우는 ]가 나오면 그 뒤에 모든 문자는 '.' 으로 채우면 된다. 2번의 경우는 사이클이 생성되면 문자 사이클을 찾은 다음 그 문자사이클을 반복하면 된다. 위를 구현하기 위해 문자의 뒤에 어떤 문자가 많이 왔는지 map을 이용해 개수를 셌다.그리고 정렬을 이용해 특정 문자의 뒤에는 어떤 문자가 오는지 계산했다. 예를 들어 [abcdeb.. 2024. 11. 23. [백준/C++] 줄다리기 (No. 31444) 문제 문제 설명 "> HTML 삽입미리보기할 수 없는 소스 풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 처음에 이 문제를 봤을 때 어떻게 풀어야할지 감이 잘 안왔다. 모든 경우를 전부 구하면 2^2000으로 시간이 초과됐고, 우선순위 큐를 이용해 그리디하게 풀어도 동점의 경우 명확하지 않다는 문제가 있었기 때문이다. 고민을 하다 힌트를 보니 이분탐색으로 문제를 풀 수 있겠다는 생각이 들었다. 먼저 두 팀의 팀워크 점수를 A값보다 크거나 같게 만들 수 있는지 검사한다.그러면 같은 팀이 된 사람들의 점수가 A보다 크거나 같아야 하므로, i번째 사람과 j번째 사람의 팀워크 점수가 A보다 작다면 두 사람은 같은 팀이 되면 안된.. 2024. 11. 19. 이전 1 다음 반응형
