본문 바로가기

Problem Solving83

[Python]2156. 포도주 시식 https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규칙이 있다. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다. 연속으로 놓여 있는 3잔을 모두 마실 수는 없다. 효주는 될 수 있는 대로 많은 양의 포도주를 맛보기 위해서 어떤 포도주 잔을 선택해야 할지 고 www.acmicpc.net 1차원 DP 1234567891011121314n = int(input())WINE = [0]+[int(input()) for _ i.. 2019. 4. 4.
[Python]9465. 스티커 https://www.acmicpc.net/problem/9465 9465번: 스티커 문제 상근이의 여동생 상냥이는 문방구에서 스티커 2n개를 구매했다. 스티커는 그림 (a)와 같이 2행 n열로 배치되어 있다. 상냥이는 스티커를 이용해 책상을 꾸미려고 한다. 상냥이가 구매한 스티커의 품질은 매우 좋지 않다. 스티커 한 장을 떼면, 그 스티커와 변을 공유하는 스티커는 모두 찢어져서 사용할 수 없게 된다. 즉, 뗀 스티커의 왼쪽, 오른쪽, 위, 아래에 있는 스티커는 사용할 수 없게 된다. 모든 스티커를 붙일 수 없게된 상냥이는 각 스티커에 점 www.acmicpc.net 고민하다가 강의를 듣고 푼 문제. 풀면서 배운 점 1. 굳이 DP의 index를 가지고 상태 표현을 다 할 필요가 없다. 기존 방법, i .. 2019. 4. 4.
[Python]10844. 쉬운 계단 수 https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 계단이라는 특성으로 인해서 문자열 비교 없이 DP를 이용해서 풀 수 있다. 단, 2차원 DP를 이용하는 것이 편리하다. 점화식으로 풀어보면 다음과 같다. DP[i][0] = DP[i-1][1] DP[i][1] = DP[i-1][0] + DP[i-1][2] DP[i][2] = DP[i-1][1] + DP[i-1][3] ... DP[i][8] = DP[i-1][7] + DP[i-1][9] DP[i][9] = DP[i-1][8] DP[1]을 미리 초기화하여 별도의 예외처리를 하지 않는다. 1 2 3 4 5 6 7 8.. 2019. 4. 4.
[Python]15990. 1,2,3 더하기 5 https://www.acmicpc.net/problem/15990 15990번: 1, 2, 3 더하기 5 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net 1차원의 DP로 풀 수 있긴 한데.. 시간이 매우매우 많이 걸린다..!! 문제 조건에 따르면 끝 자리 수와 비교하여 다를때만 연산을 해줘야 하기 때문. 따라서 2차원 DP 를 이용해서 조건을 쪼개본다. DP[i][1] = DP[i - 1][2] + DP[i - 1][3] # 현재 1은 1단계 전의 2 또는 3 에 붙을 수 있다. DP[i][2] = DP[i - 2][1] + DP[i - 2][3] # 현재 2은 2단계 전의 1 또는 3 에 붙을 수.. 2019. 4. 3.
[Python]16194. 카드 구매하기 2 https://www.acmicpc.net/problem/16194 16194번: 카드 구매하기 2 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 점화식 dp[i] 를 구하기 위해선 p[1] + dp[i-1] p[2] + dp[i-2] p[3] + dp[i-3] ... p[j] + dp[i-j] 까지 구해야 하며, 주어진 문제조건에 따라 이 중 에서 가장 작은 값이 dp[i]가 된다. 다시 말해, dp[i] = min(p[1] + dp[i-1], p[2] + dp[i-2], p[3] + dp[i-3], ... , p[j] + dp[i-j]) 여.. 2019. 4. 3.
[Python]1463. 1로 만들기 https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 #Top-down 방식 : 재귀호출 이용 import sys sys.setrecursionlimit(10000000) #재귀 한도를 늘려준다. RecursionError 방지 def dp(x): if x == 1: m[x] = 0 return m[x] if m[x] > 0: return m[x] m[x] = dp(x-1)+1 # 빼기 1 연산, 메모이제이션 + 초기화 기능 if .. 2019. 4. 2.
[Python]3055. 탈출 https://www.acmicpc.net/problem/3055 3055번: 탈출 문제 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제일 친한 친구인 비버의 굴로 가능한 빨리 도망가 홍수를 피하려고 한다. 티떱숲의 지도는 R행 C열로 이루어져 있다. 비어있는 곳은 '.'로 표시되어 있고, 물이 차있는 지역은 '*', 돌은 'X'로 표시되어 있다. 비버의 굴은 'D'로, 고슴도치의 위치는 'S'로 나 www.acmicpc.net 물이 미리 차오르는 시간을 구한다음, 고슴도치를 움직이도록 한다. 12345678910111213141516171819202122232425.. 2019. 4. 2.
[Python]2206. 벽 부수고 이동하기 https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다. 만약에 이동하는 도중에 한 개의 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 한 개 까지 부수고 이동 www.acmicpc.net 1234567891011121314151617181920212223242526272829303132333435363738394.. 2019. 4. 2.
[Python]1261. 알고스팟 https://www.acmicpc.net/problem/1261 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미한다. (1, 1)과 (N, M)은 항상 뚫려있다. www.acmicpc.net 이 문제의 경우 주변이 '0' 이면 가중치가 0, 주변이 '1' 이면 가중치가 1이다. 따라서 일반적인 Queue를 사용한 BFS는 절대 풀 수 없고 Deque을 이용해서 가중치가 0 일땐 앞에다 추가하고 가중치가 1일땐 뒤에다가 추가해줘야 한다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18.. 2019. 4. 2.
728x90
반응형

티스토리툴바