BOJ81 백준(BOJ) 3866 풍선 수집(Python) 2차원 DP 문제. 가로 길이는 전체 풍선의 개수, 세로 길이는 현재 로봇에 달려 있는 풍선의 개수로 2차원 DP 리스트를 설정했다. 당연히 풍선은 빨리 떨어지는 순으로 받아줘야 하고, 첫 풍선은 선택지 없이 집에서 출발해 받아줘야 한다. 그 다음부터 떨어지는 풍선에 대해서는 2가지의 선택지가 존재한다. 풍선을 집에 두고 받을 것인지, 그냥 받으러 갈 것인지. 이를 DP에 적용해주면 된다. i가 전체 풍선의 개수만큼의 반복문의 인자, j가 로봇에 달릴 수 있는 풍선의 개수만큼의 반복문의 인자라고 하면 첫 번째 경우 풍선의 개수가 1개로 변하는 과정이므로 dp[1][i+1]=min(dp[1][i+1],dp[j][i]+p+x)라는 점화식을 세울 수 있다. 두 번째 경우 풍선의 개수가 (현재 풍선의 개수).. 2022. 7. 8. 백준(BOJ) 1132 합(Python) 뻔한 그리디 문제였다. 솔직히 그리디에 굉장히 자신이 없어서 그냥 다른 거 풀까 싶었는데, 취약점을 보완하기로 목표를 잡았기 때문에 그냥 도전했다. 해결 방법은 간단하다. ABC=100A+10B+C BCA=100B+10C+A ABC+BCA=101A+110B+11C 이런 식으로 입력값을 모두 정리한 다음, 계수가 낮은 순으로 수를 배정한다. 합이 최대가 되어야 하므로 가장 많이 등장하는 알파벳 순으로 큰 수를 배정한다면 자연스럽게 합이 가장 커지는 구조이다. 계수를 구한 다음 정렬할 때는 최소 힙을 사용했다. 사실 그냥 리스트에서 sort()하면 될 것 같은데 이런저런 자료구조를 끌어다 쓰면서 익숙해지려고 겉멋 좀 부렸다. 수를 배정할 때는 먼저 0이 될 수 있는 알파벳인가를 먼저 확인해 가능하다면 0을 .. 2022. 7. 8. 백준(BOJ) 1022 소용돌이 예쁘게 출력하기(Python) 생각해줘야 할 부분들이 많아서 조금 까다로웠지만 나름 재미있었다. 처음에는 일단 다 그려놓고 입력받은 사이즈에 맞춰서 출력하면 되지 않을까 싶었는데, 소용돌이의 최대 크기가 10000x10000이라 다 그리다간 시간 초과 아니면 메모리 초과 둘 중 하나는 무조건 뜰 거라고 생각했다. 따라서 연산 횟수를 줄이는게 불가피했는데, 어떻게 줄여볼까 하다가 (0,0)을 기준으로 오른쪽 아래 대각선이 모두 제곱수인 걸 이용하기로 했다. 사실 처음에는 직관으로 제곱수를 골라 해결한 감이 있지만, 곰곰히 생각해보니 소용돌이의 한 cycle이 제곱수로 끝나기 때문에 제곱수를 기준으로 문제를 해결하는 것이 맞다고 생각했다. 대각선이니까 x,y좌표는 똑같고, 좌표값을 n이라고 하면 그 칸에 오는 제곱수는 (2*n+1.. 2022. 7. 8. 이전 1 ··· 11 12 13 14 다음
