본문 바로가기
728x90

알고리즘316

[python] 백준 1700 멀티탭 스케줄링 https://www.acmicpc.net/problem/1700 1700번: 멀티탭 스케줄링 기숙사에서 살고 있는 준규는 한 개의 멀티탭을 이용하고 있다. 준규는 키보드, 헤어드라이기, 핸드폰 충전기, 디지털 카메라 충전기 등 여러 개의 전기용품을 사용하면서 어쩔 수 없이 각종 전 www.acmicpc.net 문제 해결 순서대로 멀티탭을 꽂고 빼고 해야한다. 뒤에 같은 종류가 있으면 안빼고 바로 연결하면 된다. 혹은 멀티탭에 비어있는 것이 있으면 꽂으면 된다. 만약 현재 연결해야 하는 것이 있고 멀티탭에 연결되어 있는 물건 중 같은 종류가 없으면 한 종류의 물건을 빼야한다. 빼야 하는 것은 뒤에 물건들을 보고 연결할 필요가 없거나 가장 늦게 연결할 필요가 있는 것을 제거하는 것이 낫다. CODE fro.. 2023. 3. 14.
[python] 백준 1783 병든 나이트 https://www.acmicpc.net/problem/1783 1783번: 병든 나이트 첫째 줄에 체스판의 세로 길이 N와 가로 길이 M이 주어진다. N과 M은 2,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 문제 해결 bfs로 풀면 끝이라고 생각했지만 시간초과가 났다. bfs, dfs로 시간초과가 나면 결국 dp를 이용해야한다고 생각했다. 어느 방향으로 움직이던 오른쪽으로 이동을 해야한다. 열이나 행이 1칸이면 무조건 움직일 수 없기 때문에 답은 1 행이 두칸이면 열을 2칸 움직여야하기 때문에 열이 최소 3열 이상 있어야 움직인다. 4번 이상 움직이려면 움직일 수 있는 방법으로 한번씩 움직여야 한다. (-2,1),(2,1),(1,2),(-1,2) =>total (0.. 2023. 3. 14.
[python] 백준 1343 폴리오미노 https://www.acmicpc.net/problem/1343 1343번: 폴리오미노 첫째 줄에 사전순으로 가장 앞서는 답을 출력한다. 만약 덮을 수 없으면 -1을 출력한다. www.acmicpc.net 문제 해결 X가 연속 4번 나올 수 있으면 'AAAA'로 교체한다. X가 연속 2번 나오고 '.'이 나오거나 끝나게 되면 'BB'로 교체한다. X가 연속으로 홀수번 나오면 교체 불가능으로 -1 출력 CODE import sys input = sys.stdin.readline board = list(input().rstrip()) ans = [] cnt = 0 for i in range(len(board)): if board[i] == 'X': cnt += 1 if cnt == 4: for _ in r.. 2023. 3. 14.
[python] 백준 2011 암호코드 https://www.acmicpc.net/problem/2011 2011번: 암호코드 나올 수 있는 해석의 가짓수를 구하시오. 정답이 매우 클 수 있으므로, 1000000으로 나눈 나머지를 출력한다. 암호가 잘못되어 암호를 해석할 수 없는 경우에는 0을 출력한다. www.acmicpc.net 문제 해결 각 자리수 숫자를 분석해야한다. 알파벳으로 바꿀 때 해석의 가지수에 영향을 주는 것은 바로 앞에 수 하나이다. 하나씩 분석해서 이전의 수와 연결해서 10이상 26이하가 나오면 다른 암호로 해석할 여지가 있다. DP를 이용할 것이다. DP[i]는 i번째 수까지 봤을 때 해석의 가지수이다. 바로 앞에 수와 독립적으로 해석하는 가지수는 dp[i-1]이고 연결해서 해석하는 가지수는 dp[i-2]이다. CODE .. 2023. 3. 14.
728x90