파이썬

📌 문제 N개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 버스가 M개 있다. 각 버스는 A, B, C로 나타낼 수 있는데, A는 시작도시, B는 도착도시, C는 버스를 타고 이동하는데 걸리는 시간이다. 시간 C가 양수가 아닌 경우가 있다. C = 0인 경우는 순간 이동을 하는 경우, C < 0인 경우는 타임머신으로 시간을 되돌아가는 경우이다. 1번 도시에서 출발해서 나머지 도시로 가는 가장 빠른 시간을 구하는 프로그램을 작성하시오. 📌 입력 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 ..

📌 문제 돌 게임은 두 명이서 즐기는 재밌는 게임이다. 탁자 위에 돌 N개가 있다. 상근이와 창영이는 턴을 번갈아가면서 돌을 가져가며, 돌은 1개, 3개 또는 4개 가져갈 수 있다. 마지막 돌을 가져가는 사람이 게임을 이기게 된다. 두 사람이 완벽하게 게임을 했을 때, 이기는 사람을 구하는 프로그램을 작성하시오. 게임은 상근이가 먼저 시작한다. 📌 입력 첫째 줄에 N이 주어진다. (1 ≤ N ≤ 1000) 📌 출력 상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY을 출력한다. 📌 문제 풀이 👨‍🏫 접근 문제가 꽤 어려웠다. 조건을 이해하기가 어려웠기 때문이다. 문제를 분석해보자면, 이 게임은 SK의 입장에서 풀이해야 한다. 모든 참가자가 자신이 이길 수밖에 없는 구조로 게임을 하는데, 선공이 ..

📌 문제 상근이와 선영이가 다른 사람들이 남매간의 대화를 듣는 것을 방지하기 위해서 대화를 서로 암호화 하기로 했다. 그래서 다음과 같은 대화를 했다. 상근: 그냥 간단히 암호화 하자. A를 1이라고 하고, B는 2로, 그리고 Z는 26으로 하는거야. 선영: 그럼 안돼. 만약, "BEAN"을 암호화하면 25114가 나오는데, 이걸 다시 글자로 바꾸는 방법은 여러 가지가 있어. 상근: 그렇네. 25114를 다시 영어로 바꾸면, "BEAAD", "YAAD", "YAN", "YKD", "BEKD", "BEAN" 총 6가지가 나오는데, BEAN이 맞는 단어라는건 쉽게 알수 있잖아? 선영: 예가 적절하지 않았네 ㅠㅠ 만약 내가 500자리 글자를 암호화 했다고 해봐. 그 때는 나올 수 있는 해석이 정말 많은데, 그..

📌 문제 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자. 📌 입력 첫째 줄에 N(1 ≤ N ≤ 30)이 주어진다. 📌 출력 첫째 줄에 경우의 수를 출력한다. 📌 문제 풀이 👨‍🏫 접근 재귀를 통해서 완성된 조건을 풀 수 있을 것 같아보였다. 그런데 시간이 좀 오래 걸릴 것 같아서 DP를 사용했다. DP가 사용 가능한 이유는 이전 값을 참고하여 현재의 값을 구할 수 있기 때문이다. 일단 3 X 2의 타일이 있을 때, 위와 같이 3개의 배치가 가능하다. 그 다음 3X3 의 타일 배치를 구하려고 했는데, 절대로 배치를 할 수가 없었다. 직관적으로 생각해보면, 3X3은 9개의 타일이 필요한데, 2X1 타일을 아무리 배치한들 8이라는 짝수로 채워지기 때문에 남은 타일 1개를 절대 ..