[Python] 2666 - 벽장문의 이동 (골드5)
·
Coding Test/Solution
1. 문제 설명 https://www.acmicpc.net/problem/2666 2666번: 벽장문의 이동 첫 번째 줄에 벽장의 개수를 나타내는 3보다 크고 20보다 작거나 같은 하나의 정수, 두 번째 줄에 초기에 열려있는 두 개의 벽장을 나타내는 두 개의 정수, 그리고 세 번째 줄에는 사용할 벽장들 www.acmicpc.net 2. 아이디어 여전히 기억에 남는 재밌는 문제였다. 속 편하게 3차원으로 풀어버렸다. 이유를 대강 서술하자면 다음과 같다. 첫 번째, cache를 1차원으로 잡고 1을 끌어오는 거리만큼 카운트를 한다. 좌하단 그림처럼 좌측에서 1을 끌어오느냐, 우측에서 1을 끌어오느냐에 따라 경우의 수를 따로 판단할 방법없음 두 번째, cache를 2차원으로 잡고 [open1][open2] 인..
[Python] 2565 - 전깃줄 (골드5)
·
Coding Test/Solution
1. 문제 설명 https://www.acmicpc.net/problem/2565 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 2. 아이디어 그렇게 쉬운 문제는 아니었는데, 그 당시에 dp 문제만 주구장창 풀어서 금방 해결했었다. 어차피 전봇대 최대 개수는 500개 이하이므로 pole은 연결된 전봇대 정보 외엔 모두 False로 할당하고 cache는 그 중에서도 유효한 전봇대를 체크해줄 리스트로써 0으로 초기화 한다. 유효한 전봇대라니? 대체 그걸 어떻게 판단한다는 것인가. 이 문제가 전봇대로 나와서 그렇지 조금..
[Python] 10835 - 카드게임 (골드5)
·
Coding Test/Solution
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)
·
Coding Test/Solution
1. 문제 설명 https://www.acmicpc.net/problem/13302 13302번: 리조트 수영이는 여름방학을 맞이하여 많은 놀이 시설이 있는 KOI 리조트에 놀러가려고 한다. 리조트의 하루 이용권의 가격은 만원이다. 하지만 리조트의 규모는 상상을 초월하여 모든 시설을 충분히 www.acmicpc.net 2. 아이디어 이렇게 경우의 수가 여러가지로 갈리면서 더 효율적인 케이스를 질문하는 문제는 대부분 dp를 활용해야 한다. 분명히 dp만으로 해결될 수 있는 문제..라고 지금은 생각하지만 예전의 나는 그렇지 않았나 보다. 괴랄하게 생겨먹은 bfs와 함께 문제를 풀었는데 그때 쓰인 아이디어가 아래와 같다. (지금 다시 읽어보니까 DP조차 아님 ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ) 아이디어를 ..