분류 전체보기282 1111. IQ Test (Python) 1111번: IQ Test 다음 수를 출력한다. 만약 다음 수가 여러 개일 경우에는 A를 출력하고, 다음 수를 구할 수 없는 경우에는 B를 출력한다. www.acmicpc.net 풀이 방정식을 통하여 a와 b를 구하고 각 숫자에 * a + b를 했을 때 다음 숫자가 나오는지를 확인하면 된다. 1, 4, 13, 40 예를 들어 위의 예제에서 1a + b = 4와 4a + b =13의 방정식을 사용하여 a와 b를 구한다. 두 식을 빼면 3a = 9가 나오고 여기에서 a=3이 됨을 알 수 있다. 이를 통해 b는 1이 된다. 이제 앞에서 부터 차례대로 * 3 + 1을 하여 다음 숫자가 나오는지 확인한다. 문제를 풀 때 몇 가지 예외 처리를 해줘야 한다. N이 1인 경우 -> 뒤에 아무 숫자나 올 수 있으므로 '.. 2022. 5. 19. 2981. 검문 (Python) 2981번: 검문 트럭을 타고 이동하던 상근이는 경찰의 검문을 받게 되었다. 경찰은 상근이가 운반하던 화물을 하나하나 모두 확인할 것이기 때문에, 검문하는데 엄청나게 오랜 시간이 걸린다. 상근이는 시간 www.acmicpc.net 풀이 입력 받은 각 수 들의 차이에 대하여 최대 공약수를 구한다. 위의 예제를 보자. 입력으로 받은 [5, 17, 23, 14, 83]에 대하여 자신의 앞에 있는 숫자와의 차이를 구하면 [12, 6, 9, 69]가 나온다. 이제 이 숫자들에 대하여 차례대로 최대 공약수를 구한다. 12와 6의 최대 공약수를 구하면 6이 나온다. 다시 이 6과 9의 최대 공약수를 구하면 3이 나온다. 다시 3과 69에 대하여 최대 공약수를 구하면 3이 나온다. 최종적으로 입력으로 받은 숫자들에 대.. 2022. 5. 19. 9370. 미확인 도착지 (Python) 9370번: 미확인 도착지 (취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서 www.acmicpc.net 풀이 다익스트라를 사용하는 문제인데 문제에서 주어진 g와 h 교차로 사이에 있는 도로를 지나가는 길을 포함하는 최소 경로가 있는지에 대해서 추가적으로 판단하는 작업이 필요하다. 보통 우선순위 큐에 넣을 때 (출발점에서의 거리, 다음 출발 노드)와 같은 형태로 넣어주는 데 이렇게 해서는 특정 길을 지났는지를 판단할 수 없다. 추가적으로 g와 h 도로를 지나간 경로인지를 판단하기 위한 플래그 값이 필요하다. 위의 그림을 보면 1번에서 4번으로 가는 최소 경로 .. 2022. 5. 17. 15998. 카카오머니 (Python) 15998번: 카카오머니 만약 유효한 최소 충전 단위 M(1 ≤ M ≤ 9 * 1018)이 존재한다면, 첫 번째 줄에 M 을 출력한다. 가능한 값이 여러 가지 있다면, 그중 9 * 1018 이하인 것을 아무거나 하나 출력한다. 존재하지 않는다면 www.acmicpc.net 풀이 계좌에서 충전이 필요한 출금 작업을 할 때마다 충전에 필요한 최대 금액들에 대한 최대 공약수를 구하고 구한 값을 M으로 설정했을 때 로그에 모순이 생기지 않는지를 체크한다. 문제의 예제에서 충전이 필요한 출금 작업은 두 건 존재한다. (1)번 로그의 경우 충전이 필요한 첫 출금 작업이므로 계산에 필요한 값들을 기록하면 된다. 여기에서 필요한 값은 충전해야 하는 20,000원에 대한 정보와 출금 후 남은 잔액인 4,500원이다. (.. 2022. 5. 17. 2293. 동전 1 (Python) 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 풀이 1차원 dp를 사용하여 문제를 해결할 수 있다. dp[value]는 value를 만들 수 있는 동전 조합의 수를 의미한다. dp 배열의 모든 값을 0으로 초기화하여 만든 후 dp[0]은 1로 설정한다. 이는 가치 0을 만들 수 있는 조합은 아무 동전도 사용하지 않는 하나의 경우의 수가 있기 때문이다. 문제의 점화식은 다음과 같다. value는 현재 살펴볼 가치의 합을 의미하고 coin은 현재 사용할 동전의 가치를 의미한다. dp[value + coin] +=.. 2022. 5. 15. 6087. 레이저 통신 (Python) 6087번: 레이저 통신 크기가 1×1인 정사각형으로 나누어진 W×H 크기의 지도가 있다. 지도의 각 칸은 빈 칸이거나 벽이며, 두 칸은 'C'로 표시되어 있는 칸이다. 'C'로 표시되어 있는 두 칸을 레이저로 통신하기 위해서 www.acmicpc.net 풀이 BFS를 통해서 C에서 C로 갈 때 필요한 거울 개수의 최솟값을 구할 수 있다. BFS를 위한 큐에는 (행, 열, 이전에 이동했던 방향, 사용한 거울의 개수)와 같은 튜플의 형태로 값을 넣어줬다. 이전에 이동했던 방향을 넣어준 이유는 기존에 이동했던 방향 그대로 이동할 때는 거울을 사용하지 않고 이동하고 90도 방향으로 이동할 때는 거울을 사용하기 때문에 이를 체크하기 위해 사용했다. 반대 방향으로 이동하는 경우는 체크하지 않고 넘어간다(예를 들어.. 2022. 5. 13. 이전 1 ··· 5 6 7 8 9 10 11 ··· 47 다음
