백준 31723번: 무빙워크 (Python)

문제링크 https://www.acmicpc.net/problem/31723 문제 총평 - 평범한 다익스트라에 아이디어 조금 첨가 문제 접근방식 - 이 문제에 경우 사실 간단합니다. - 먼저 평범한 다익스트라 처럼 간선을 받아주고 무빙워크의 반대 방향으로는 *2의 길이로 받아줍니다. - 이때 이 간선들은 버리지 말고 나중 출력을 위해 따로 모아 놓습니다. - 그리고 다익스트라를 돌리면 1에서부터의 모든 정점의 거리가 나옵니다. - 이때 따로 모아 놓았던 간선을 확인 합니다. 경우의 수 1. dist[u] >= d[v] 인 경우 2. dist[u] < d[v] 인 경우 - 이 두 경우에서 2번을 주목하면 되는데 dist[u] < d[v]라는거는 정점 1에서 u 정점으로 간 이후 u 정점에서 임의의 경로를 ..

• format_list_bulleted 알고리즘
• · 2024. 4. 14.
• textsms

백준 31537번: 출근하기 싫어 1 (Python)

문제링크 https://www.acmicpc.net/problem/31537 문제 총평 - 조합론을 몰라도 풀 수 있는 플레티넘 문제 문제 접근방식 - 총 N명의 직원이 있는데, 이 중 최대 1명이 출근하지 않아도 업무를 정상적으로 진행할 수 있다. 하지만 1명보다 많이 출근하지 않으면 업무를 정상적으로 진행할 수 없다. - 이 구절만 봐도 문제를 풀 수 있습니다. - 예를 들어 첫 번째 입력을 보겠습니다. - 총 4시간의 근무 시간 중 두명다 3시간은 근무를 해야합니다 -> 즉 각각은 1시간 씩은 쉬어야 합니다. - 즉 정답은 이 경우의 수의 곱이 됩니다. - 이 관점에서 문제의 풀이는 N명이 각각 쉬어야 하는 시간을 구하여 m에서 어느 시간대에서 쉬어야 하는지를 파악하면 됩니다. - 단 문제 조건상 ..

• format_list_bulleted 알고리즘
• · 2024. 4. 10.
• textsms

백준 31741번: 구간 덮기 (Python, Rust)

문제링크 https://www.acmicpc.net/problem/31741 문제 총평 - 문제 안에 답이있다. - 문제를 보고 이분탐색은 떠올렷는데 어떻게 쓰는 거지? 라고 생각하신 분들과 이게 왜 이분탐색이지? 라고 생각하신 분들에게 도움이 되었으면 좋겟습니다. 문제 접근방식 - 이 문제에서 가장 중요한 점은 " 최대 3개 사용하여 모두 덮으려 한다." 라는 구절입니다. - 또한 문제에서 반드시 양쪽을 포함하는 두 선분을 포함해야 합니다. -> a = E인 선분 두개가 반드시 있어야 합니다. - 이 구절에서 최대 3개가 가장 중요한데 그 이유는 간단합니다. - 다음 문제에서 모든 구간을 겹칠 수 있는 방식은 3개 입니다 1. 한 개의 선분이 전 구간을 덮는 경우 a = E -> 이 경우에는 무조건 오..

• format_list_bulleted 알고리즘
• · 2024. 4. 9.
• textsms

백준 31721번: 수강신청 (Python)

문제링크 https://www.acmicpc.net/problem/31721 문제 총평 - 아이디어의 중요성 문제 접근방식 - 이 문제의 경우 그리디를 이용해 이 문제만의 풀이법을 짜야하는 애드 혹 문제입니다. - 먼저 n개의 수강과목들을 받으면서 a >= b 인경우 무조건 정답에 +1을 해줍니다. - 그 이유는 a > b인 경우 달구가 반드시 수강신청이 가능하고 a == b인 경우 달구가 수강신청을 해야만 수강 정원이 가득 차므로 풀이에 신경쓰지 않고 정답에 +1을 해주면 됩니다. - 그 이외에는 a 만 리스트에 넣어줍니다, 그 이유는 b는 사실상 의미없는 값이므로 a만 저장해 둡니다. - 그 후 역정렬을 해주고 그 이유는 이후에 설명드리겟습니다. - 이제 리스트가 빌때까지 반복문을 돌립니다. 1. 먼..

• format_list_bulleted 알고리즘
• · 2024. 4. 7.
• textsms

백준 4342번: 유클리드 게임 (Python)

문제링크 https://www.acmicpc.net/problem/4342 문제 총평 - 수학을 못하면 고생한다 수정 후 풀이 - 실제로는 이 문제는 게임이론에 관한 문제입니다. - 또한 이 문제는 특정 인물이 주도권을 잡는 순간 무조건 그 게임을 이길 수 있는 형태의 게임입니다. - 그러므로 처음으로 게임의 주도권을 잡는 순간인 큰수에서 뺄수있는 작은수가 2개 이상(a//b > 1)일 때 자기 턴을 가지고 있는 쪽이 반드시 승리하게 됩니다. while 1: a,b = map(int, input().split()) if a == 0 and b == 0: break a,b = max(a,b), min(a,b) ans = 'A' while a%b: if a//b > 1: print(ans,'wins') br..

• format_list_bulleted 알고리즘
• · 2024. 2. 11.
• textsms

백준 25319번: Twitch Plays VIIIbit Explorer

문제링크 https://www.acmicpc.net/problem/25319 문제 총평 - 간단한 구현 문제, 단 BFS 또는 DFS로 오해하면 안된다. 문제 접근방식 - 문제를 보자마자는 DFS 또는 BFS로 생각했지만 시간복잡도가 너무 클거같다고 생각함. - 어처피 스페셜 저지 문제이고 최소값을 구할 필요가 없으므로 가능한 경우 무조건 그 장소로 가도록 하였음 정답코드 import sys;I = sys.stdin.readline from collections import defaultdict n,m,l = map(int,I().rstrip().split()) arr = [list(I().rstrip()) for _ in range(n)] s = I().rstrip() dic = defaultdict(..

• format_list_bulleted 알고리즘
• · 2024. 1. 22.
• textsms