전체 글

[Python] 10835 - 카드게임 (골드5)

1. 문제 설명 https://www.acmicpc.net/problem/10835 10835번: 카드게임 첫 줄에는 한 더미의 카드의 개수를 나타내는 자연수 N(1 ≤ N ≤ 2,000)이 주어진다. 다음 줄에는 왼쪽 더미의 카드에 적힌 정수 A(1 ≤ A ≤ 2,000)가 카드 순서대로 N개 주어진다. 그 다음 줄에는 오 www.acmicpc.net 이 문제.. 바보같이 sys.setrecursionlimit = 10**7 이라고 입력해놓고 '왜 자꾸 틀렸지??'하고 샷건치던 문제였다.. 2. 아이디어 문제가 엄청나게 길지만 요약하면 결국 둘 다 버리거나, 경우에 따라 왼쪽만 버릴거냐, 오른쪽만 버릴거냐를 판단하고 최댓값을 알아보라는 문제다. (두 줄 요약인데 진짜 이게 다다) 이번에도 '모든 경우의..

[Python] 13302 - 리조트 (골드4)

1. 문제 설명 https://www.acmicpc.net/problem/13302 13302번: 리조트 수영이는 여름방학을 맞이하여 많은 놀이 시설이 있는 KOI 리조트에 놀러가려고 한다. 리조트의 하루 이용권의 가격은 만원이다. 하지만 리조트의 규모는 상상을 초월하여 모든 시설을 충분히 www.acmicpc.net 2. 아이디어 이렇게 경우의 수가 여러가지로 갈리면서 더 효율적인 케이스를 질문하는 문제는 대부분 dp를 활용해야 한다. 분명히 dp만으로 해결될 수 있는 문제..라고 지금은 생각하지만 예전의 나는 그렇지 않았나 보다. 괴랄하게 생겨먹은 bfs와 함께 문제를 풀었는데 그때 쓰인 아이디어가 아래와 같다. (지금 다시 읽어보니까 DP조차 아님 ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ) 아이디어를 ..

[Python] 1052 - 물병 (실버1)

1. 문제 설명 https://www.acmicpc.net/problem/1052 1052번: 물병 지민이는 N개의 물병을 가지고 있다. 각 물병에는 물을 무한대로 부을 수 있다. 처음에 모든 물병에는 물이 1리터씩 들어있다. 지민이는 이 물병을 또 다른 장소로 옮기려고 한다. 지민이는 한 번 www.acmicpc.net 2. 아이디어 이 문제를 처음 접했을 때, 규칙성을 파악하다가 비트 연산을 쓰면 편하겠다 싶긴 했는데 비트 연산을 많이 안 써봤던 터라 컨트롤하는데 애 좀 먹었었다. '여기서 대체 왜 비트가 나오나요?'라는 질문을 할 수 있는데 아래의 그림을 보면 이해할 수 있다. 그림을 보면 2의 거듭제곱은 곧 1병으로 합칠 수 있음 의미한다. N이 2의 거듭제곱으로 주어진다면 추가해야 하는 물병 수..

[Python] 10844 - 쉬운 계단 수 (실버1)

1. 문제 설명 https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 2022 연세대 알고리즘 대회에 나온 문제에서 막혔어서 끝나고 이 문제를 풀어봤었다. 물론 이걸 푼다고 그 문제가 풀리진 않았다... 2. 아이디어 테스트 케이스에서 힌트를 하나 얻어가야 하는데 input이 1일 때, output이 9가 나온다. 문제 조건에선 0으로 시작하는 수는 계단 수가 아니라고 했으므로 이후에는 0이 나올 수 도 있다. 계단수는 1~9에서 시작해서 0~9범위에서 움직이는 수열이다. 이 문제는 dp[N번째 계단][현재 위치] = 경우의 수로 풀면 쉽게 풀린다. 1번 (ind..