본문 바로가기

Algorithm 💡272

[백준 1417번] 국회의원 선거 https://www.acmicpc.net/problem/1417import sysimport heapqinput = sys.stdin.readline# 국회의원 선거를 조작# 다솜이의 기계는 각 사람들이 누구를 찍을 지 미리 읽을 수 있다. # 어떤 사람이 누구를 찍을 지 정했으면, 반드시 선거때 그 사람을 찍는다.# 형택구에 나온 국회의원 후보는 N명# 다솜이는 이 기계를 이용해서 그 마을의 주민 M명의 마음을 모두 읽었다.# 다솜이는 기호 1번# 자신을 찍지 않으려는 사람을 돈으로 매수해서 국회의원에 당선이 되게 하려고 한다.# 다른 모든 사람의 득표수 보다 많은 득표수를 가질 때, 그 사람이 국회의원에 당선# 출력 : 다솜이가 매수해야하는 사람의 최솟값N = int(input())my_vote =.. 2024. 10. 3.
[백준 2638번] 치즈 https://www.acmicpc.net/problem/2638import sysfrom collections import dequeinput = sys.stdin.readlinedx, dy = [-1,1,0,0], [0,0,-1,1]# 치즈는 실내온도에 내어놓으면 공기와 접촉하여 천천히 녹는다# 각 치즈 격자(작은 정사각형 모양)의 4변 중에서 적어도 2변 이상이 실내온도의 공기와 접촉한 것은 정확히 한시간만에 녹아 없어져 버린다N, M = map(int,input().split())# 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 표시# 모눈종이의 맨 가장자리에는 치즈가 놓이지 않는 것으로 가정# 출력 : 입력으로 주어진 치즈가 모두 녹아 없어지는데 걸리는 정확한 시간area = [.. 2024. 10. 3.
[백준 6603번] 로또 https://www.acmicpc.net/problem/6603import sysinput = sys.stdin.readline# {1, 2, ..., 49}에서 수 6개를 고른다# 49가지 수 중 k(k>6)개의 수를 골라 집합 S를 만든 다음 그 수만 가지고 번호를 선택하는 것def combinations(arr, k): cases = [] def dfs(elements,index): if len(elements) == k: cases.append(elements) return for i in range(index+1,len(arr)): dfs(elements+[arr[i]],i) dfs([].. 2024. 10. 3.
[백준 21609번] 상어 중학교 https://www.acmicpc.net/problem/21609# 초기에 격자의 모든 칸에는 블록이 하나씩 들어있고, 블록은 검은색 블록, 무지개 블록, 일반 블록이 있다.# 일반 블록은 M가지 색상이 있고, 색은 M이하의 자연수로 표현# 검은색 블록은 -1, 무지개 블록은 0으로 표현# 블록 그룹은 연결된 블록의 집합이다. 그룹에는 일반 블록이 적어도 하나 있어야 하며, 일반 블록의 색은 모두 같아야 한다. # 검은색 블록은 포함되면 안 되고, 무지개 블록은 얼마나 들어있든 상관없다. # 그룹에 속한 블록의 개수는 2보다 크거나 같아야 하며, 임의의 한 블록에서 그룹에 속한 인접한 칸으로 이동해서 그룹에 속한 다른 모든 칸으로 이동할 수 있어야 한다.# 블록 그룹의 기준 블록은 무지개 블록이 아닌 .. 2024. 10. 1.
[백준 17141번] 연구소 2 https://www.acmicpc.net/problem/17141# 연구소의 특정 위치에 바이러스 M개를 놓을 것이고, 승원이의 신호와 동시에 바이러스는 퍼지게 된다.# 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다.# 0은 빈 칸, 1은 벽, 2는 바이러스를 놓을 수 있는 칸# 일부 빈 칸은 바이러스를 놓을 수 있는 칸이다. 바이러스는 상하좌우로 인접한 모든 빈 칸으로 동시에 복제되며, 1초가 걸린다.# 연구소의 모든 빈 칸에 바이러스가 있게 되는 최소 시간을 출력# 바이러스를 어떻게 놓아도 모든 빈 칸에 바이러스를 퍼뜨릴 수 없는 경우에는 -1을 출력import sysfrom collections import dequeinput = sys.stdin.readlineN, .. 2024. 10. 1.
[백준 15989번] 1, 2, 3 더하기 4 import sysinput = sys.stdin.readlinet = int(input())dp = [1]*10001for i in range(2,10001): dp[i] += dp[i-2]for i in range(3,10001): dp[i] += dp[i-3]for i in range(t): print(dp[int(input())]) 이번 문제는 주어진 숫자를 1, 2, 3을 사용하여 만들 수 있는 경우의 수를 구하는 문제이다. 1부터 10까지의 케이스를 구하다보니 패턴이 존재할 것 같다는 예감이 들었고, DP문제라는 것을 감으로 알 수 있었다. 하지만 점화식을 찾는 것이 너무 어려워서 다른 블로그를 참고하였다. 먼저 모든 숫자는 1로만 채우는 방법이 존재하기 때문에 DP테이블을 1.. 2024. 9. 26.

티스토리툴바