Dev_Diary

https://www.acmicpc.net/problem/17142어떻게 시작 바이러스 위치를 샘플링 할까 고민하시겠지만 모든 경우를 진행해보면 됩니다. 최대 바이러스 10 개중 M 개를 뽑는 경우의 수 중 최대는 M == 5 인 경우일텐데 252 가지 밖에 안되기 때문에 모두 진행한다고 해도 최악의 경우 252*50*50 = 630,000 번의 계산이 일어납니다. 때문에 모든 경우를 계산해도 아주 넉넉하게 통과할 수 있습니다. M 개의 바이러스를 뽑았다면 모든 M 개의 점에서 동시에 BFS 를 진행하며 최솟값을 갱신해주면 됩니다.import sysfrom collections import dequefrom itertools import combinationsinput = sys.stdin.readlin..

https://www.acmicpc.net/problem/1759조합 문제입니다.문자를 정렬 후 조합시키면 조합된 문자열이 나오니 이들 중 조건에 맞는 것을 필터링하면 됩니다.import sysfrom itertools import combinationsinput = sys.stdin.readlinedef solution(L, C, chr): # 조합 for comb in combinations(chr, L): # 한 개의 모음과 두 개의 자음 m = 0 j = 0 for c in comb: if c in 'aeiou': m += 1 else: j +=..

https://www.acmicpc.net/problem/1146브루트 포스나 BFS 의 식으로도 풀 수 있지만 시간제한에 걸리게 됩니다.다른 방법을 찾아봅시다. 우리는 N 명의 학생을 줄세워야 합니다.그 중 번호가 가장 큰 N 번째 학생을 P 번째 순서에 줄 세우는 경우를 생각해보겠습니다.그럼 남은 N-1 명의 학생을 줄 세워야 하는데, 어차피 수의 대소만이 중요하기 때문에 지그재그 패턴만 맞으면 어떤 학생이 어디에 서던 중요하지 않습니다.즉 N 번째 학생을 P 번째 세우고 양 옆에 남은 학생들을 다시 줄세우는 작은 단계로 쪼갤 수 있습니다.즉 이 문제를 DP 로 풀 수 있습니다. N 명의 학생 중 P 번째 자리에 N 번째 학생을 줄세운다고 생각하겠습니다.해당 경우를 A_NP 라고 부르겠습니다. P 가..