문제 백준 9205 맥주 마시면서 걸어가기 풀이 ( 파이썬 ) https://www.acmicpc.net/problem/9205 9205번: 맥주 마시면서 걸어가기 송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다. www.acmicpc.net 풀이 다익스트라를 적용해서 문제를 풀었더니 됐다. q를 돌릴 때 마다 deque에서 나오는 좌표와 목적지와의 거리의 맨해튼 거리를 확인 후 안에 있다면 flag를 True로 바꿔 happy를 출력하게 한다. from collections import deque import sys input = sys.stdin.readline t..

문제 백준 2931 가스관 풀이 ( 파이썬 ) https://www.acmicpc.net/problem/2931 2931번: 가스관 www.acmicpc.net 풀이 일단 입력을 받을 때 M이나 Z인 경우를 입력으로 받았다. 그리고 M과 Z인 좌표에서 시작하게 되는데 위 사진과 같이 일반적인 상황에서는 둘 중 하나에서 4방향 중 한 곳에 무조건 파이프를 갖게 된다 여기서 파이프를 갖게 된다는 말은 단순히 파이프가 있는 것이 아니라 흐를 수 있는 파이프가 있는 것이다. 그러므로 차례로 경로를 찾아가는 코드를 작성하면 된다. 하지만, 위의 경우처럼 옆에 둘 다 파이프가 없는 경우가 존재하는데, 이런 경우이다 그래서 flag라는 변수로 이 두 경우가 생길 수 있음을 생각하고 처음 나온 그림의 경우는 True로..

문제 백준 2623 음악프로그램 풀이 ( 파이썬 ) https://www.acmicpc.net/problem/2623 2623번: 음악프로그램 첫째 줄에는 가수의 수 N과 보조 PD의 수 M이 주어진다. 가수는 번호 1, 2,…,N 으로 표시한다. 둘째 줄부터 각 보조 PD가 정한 순서들이 한 줄에 하나씩 나온다. 각 줄의 맨 앞에는 보조 PD가 담당한 www.acmicpc.net 풀이 순서라는 말을 들었을 때 단순히 위상정렬을 사용하면 되겠지라고 생각했는데 안 되는 경우를 생각해보니 싸이클이 생겼을 때였다. 그러므로 위상정렬을 하기 전에 먼저 싸이클이 있는지 확인하고 싸이클이 있다면 0을 출력하고 아니라면 순서를 출력하면 된다. 싸이클을 판단할 때 어떤 노드를 골라야하나 생각해서 위상정렬의 시작은 차수..

문제 백준 2252 줄 세우기 풀이 ( 파이썬 ) https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net 풀이 뭔가 쉬워보이듯 어떻게 해야하나 했는데 순서라는 말이 나왔을 때 위상정렬을 생각하면 되는 것 같다. 단순히 위상정렬을 적용하니 풀렸다. from collections import deque import sys input=sys.stdin.readline n,m=map(int,input().split(..

문제 백준 3980 선발 명단 풀이 ( 파이썬 ) https://www.acmicpc.net/problem/3980 3980번: 선발 명단 각각의 테스트 케이스에 대해서, 모든 포지션의 선수를 채웠을 때, 능력치의 합의 최댓값을 출력한다. 항상 하나 이상의 올바른 라인업을 만들 수 있다. www.acmicpc.net 풀이 단순하게 백트래킹을 이용해서 문제를 풀었다. visited는 해당 선수를 썼는지 안썼는지를 나타낸다. n=int(input()) ans=0 def dfs(pos,visited,deep,hap): global ans if deep==11: ans=max(ans,hap) # print(ans) return for i in pos[deep]: score,po,pe=i if po==deep a..

문제 백준 9421 소수상근수 풀이 ( 파이썬 ) https://www.acmicpc.net/problem/9421 9421번: 소수상근수 양의 정수 n의 각 자리수의 제곱의 합을 계산한다. 그렇게 해서 나온 합도 각 자리수의 제곱의 합을 계산한다. 이렇게 반복해서 1이 나온다면, n을 상근수라고 한다. 700은 상근수이다. 72 + 02 + 02 = www.acmicpc.net 풀이 지금까지 알고리즘 문제를 풀 때 소수 관련 풀이가 두 가지가 있었는데 이번 문제는 에라토스테네스의 체를 이용한 문제였다. 먼저 범위 안의 소수들을 primes에 넣고 이 소수들이 소수상근수인지 판별하여 확인했다. 소수상근수인지 확인할 때는 각 자리수의 곱을 더한 것이 또 나온다면 반복되는 것이므로 dict을 이용해 dict..