본문 바로가기
728x90

분류 전체보기424

[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.
[python] 백준 14442 벽 부수고 이동하기 2 https://www.acmicpc.net/problem/14442 14442번: 벽 부수고 이동하기 2 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자. www.acmicpc.net 문제 해결 (0,0)에서 (n-1,m-1)까지 이동하는 문제 갈 수 있는 길이 있고 없는 길이 있다. 하지만 예외적으로 k번 갈 수 없는 길을 갈 수 있다. 따라서 visited[i][j]에서 예외포인트 k번 까지 가능하다는 것에서 visited[i][j][k]의 방문 여부를 확인하는 것이 편하다. visited[i][j][k]의 값은 (i,j)까지 벽을 깰 수.. 2023. 3. 14.
[python] 백준 1213 팰린드롬 만들기 https://www.acmicpc.net/problem/1213 2023. 3. 13.
728x90