https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 다이나믹 프로그래밍 문제.. 점화식 세우는 게 너무 어렵다 dp[i] = max(dp[i-2]+scores[i], dp[i-3]+scores[i-1]+scores[i]) 이게 아니라 dp[i] = max(dp[i-2]+scores[i], dp[i-3]+scores[i-1]+scores[i], dp[i-1]) 가 아닌가?! 하는 오해가 있었는데 (불리하면 현재 계단을 밟지 말아야 한다고 생각해서) 한 번에 2개..

https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 다이나믹 프로그래밍 문제다. 연속적으로 3잔의 포도주를 먹을 수 없다는 제한이 있다. i번째 포도주에 해당하는 dp값은 i번째 포도주를 마시는 경우와 마시지 않는 경우로 나눌 수 있는데 (1) i번째 포도주를 마시는 경우 (1.1) i-1번째와 i번째 포도주를 마시는 경우: i-2번째는 먹지 못하니까 dp[i-3] + wine[i-1] + wine[i] (1.2) i-1번째 포도주는 마시지 않고 i..

https://www.acmicpc.net/problem/20055 20055번: 컨베이어 벨트 위의 로봇 길이가 N인 컨베이어 벨트가 있고, 길이가 2N인 벨트가 이 컨베이어 벨트를 위아래로 감싸며 돌고 있다. 벨트는 길이 1 간격으로 2N개의 칸으로 나뉘어져 있으며, 각 칸에는 아래 그림과 같이 1부 www.acmicpc.net 각 칸의 내구도를 belt, 로봇이 있는 칸의 인덱스를 robots에 저장한다. 1-4 각 과정을 함수로 만들어 매 단계마다 반복한다. 먼저 컨베이어 벨트의 회전은 벨트와 그 위의 로봇이 이동해야 한다. 벨트의 회전은 큐를 이용해 구현했고, 로봇의 이동은 인덱스를 하나씩 증가시키는 것으로 구현했다. 이때 마지막 인덱스에 로봇이 있는 경우 +1이 아니라 처음 칸인 0으로 가야하..

https://www.acmicpc.net/problem/17144 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net 미세먼지의 양과 그 위치를 확인하는 함수, 미세먼지의 확산을 구현하는 함수, 공기청정기의 윗부분과 아랫부분의 확산을 구현하는 함수를 만들어 매 초마다 이 함수들을 실행해주었습니다. 미세먼지의 양과 위치를 확인하는 함수는 전체 방의 원소를 확인하면서 원소가 0보다 크면 위치와 양을 튜플로 저장했습니다. (행, 열, 미세먼지 양) 미세먼지의 확산을 구현하기 위해서 상하좌우가 방 안에 있고, 공기청정..

https://www.acmicpc.net/problem/2563 2563번: 색종이 첫째 줄에 색종이의 수가 주어진다. 이어 둘째 줄부터 한 줄에 하나씩 색종이를 붙인 위치가 주어진다. 색종이를 붙인 위치는 두 개의 자연수로 주어지는데 첫 번째 자연수는 색종이의 왼쪽 변 www.acmicpc.net 100*100 크기의 0으로 이루어진 행렬을 만들고 이를 도화지로 생각했습니다. 사각형 입력이 주어질 때마다 그 부분을 1로 채워줬고, 0에서 1로 바뀌는 순간 count를 하나씩 증가해줬습니다. 최종 count를 답으로 프린트했습니다. import sys def fill_square(square, board, answer): x,y = square # 사각형의 범위 for i in range(x, x+10..

https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 나누고 빼는 대신 곱하고 더하는 것으로 바꿔 풀었다. N에서 1로 줄여나가는 것이 아니라, 1에서 N으로 늘려가는 것으로 방향을 반대로 보고 풀었다. 먼저 dp를 모두 N인 리스트로 초기화해주고, index 1의 값만 0으로 바꿔준다. 1부터 N-1까지 다음을 반복한다. 현재 i에서 3 곱한 것이 N 이하면, graph[i]+1의 값과 graph[i*3] 중 최솟값 취하기 현재 i에서 2 곱한 것이 N 이하면, graph[i]+1의 값과 graph[i*2] 중 최솟값 취하기 현재 i에서 1 더한 것이 N 이하면..