본문 바로가기

백준80

백준(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.