공작소

문제 링크 : https://www.acmicpc.net/problem/2157 2157번: 여행 첫째 줄에 N(1 ≤ N ≤ 300), M(2 ≤ M ≤ N), K(1 ≤ K ≤ 100,000)가 주어진다. K는 개설된 항공로의 개수이다. 다음 K개의 줄에는 각 항공로에 대한 정보를 나타내는 세 정수 a, b, c(1 ≤ a, b ≤ N, 1 ≤ c ≤ 1 www.acmicpc.net 문제 N개의 도시가 동쪽에서 서쪽으로 순서대로 위치해 있다. 제일 동쪽에 있는 도시는 1번 도시이며, 제일 서쪽에 있는 도시는 N번 도시이다. 당신은 이와 같은 도시 중에서 M개 이하의 도시를 지나는 여행을 계획하려 한다. 여행 경로는 반드시 1번 도시에서 시작해서 N번 도시에서 끝나야 한다. 물론 이 두 도시도 M개의 ..

>> 문제 바로가기 (https://www.acmicpc.net/problem/2688) 문제 어떤 숫자가 줄어들지 않는다는 것은 그 숫자의 각 자리 수보다 그 왼쪽 자리 수가 작거나 같을 때 이다. 예를 들어, 1234는 줄어들지 않는다. 줄어들지 않는 4자리 수를 예를 들어 보면 0011, 1111, 1112, 1122, 2223이 있다. 줄어들지 않는 4자리수는 총 715개가 있다. 이 문제에서는 숫자의 앞에 0(leading zero)이 있어도 된다. 0000, 0001, 0002는 올바른 줄어들지 않는 4자리수이다. n이 주어졌을 때, 줄어들지 않는 n자리 수의 개수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 테스트 케이스의 개수 T(1

>> 문제 바로가기 (https://www.acmicpc.net/problem/17626) 문제 라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 5^2과 1^2의 합이다; 또한 4^2 + 3^2 + 1^2으로 표현할 수도 있다. 역사적으로 암산의 명수들에게 공통적으로 주어지는 문제가 바로 자연수를 넷 혹은 그 이하의 제곱수 합으로 나타내라는 것이었다. 1900년대 초반에 한 암산가가 15663 = 125^2 + 6^2 + 1^2 + 1^2라는 해를 구하는데 8초가 걸렸다는 보고가 있다. 좀 더 어려운 문제에 대해서는 56초가 걸렸다: 11339 = 105^2 + 15^2 + 8^2 + 5^..

>> 문제 바로가기 (https://www.acmicpc.net/problem/2591) 문제 1부터 34까지 수가 적힌 카드가 충분히 많이 있다. 이들 중 몇 장을 일렬로 늘어놓고, 그 숫자를 차례로 적었다. 예를 들어 아래와 같이 카드가 놓인 경우 숫자를 차례로 적으면 27123이 된다. 나중에, 적어 놓은 것에 맞게 다시 카드를 늘어놓으려고 보니, 방법이 여러 가지일 수 있다는 것을 알았다. 예를 들어 27123의 경우 아래와 같이 여섯 가지 다른 방법이 있다. 카드의 숫자를 차례로 적어 놓은 것이 주어질 때, 위와 같이 그것을 가지고 거꾸로 카드의 배열을 찾으려고 한다. 가능한 카드의 배열이 모두 몇 개인지 구하는 프로그램을 작성하시오. 입력 첫 줄에 카드의 숫자를 차례로 적어 놓은 것이 주어지며..

>> 문제 바로가기 (https://www.acmicpc.net/problem/11051) 풀이 과정 import sys import math input = sys.stdin.readline n, k = map(int, input().rstrip().split()) print(math.comb(n, k)%10007) 파이썬은 math.comb 를 사용해도 되지만... 이 문제가 실버 2인 이유가 있으므로 다른 방식으로도 풀이해보자. 해당 문제는 파스칼의 삼각형 모양을 떠올리면 쉽게 풀이할 수 있다. 파스칼의 삼각형은 바로 위의 왼쪽 수와 오른쪽 수를 더한 값이므로, 이를 DP 점화식으로 활용하여 풀이한다. import sys input = sys.stdin.readline n, k = map(int, i..

>> 문제 바로가기 (https://www.acmicpc.net/problem/17130) 문제 토끼가 정보섬에 올라왔다! 정보섬은 N행 M열의 격자로 나타낼 수 있으며, 어째서인지 여기저기에 당근이 떨어져 있다. 방금 토끼 한 마리가 정보섬 정문으로 들어왔다. 토끼의 왼쪽에선 사나운 늑대가 쫓아오고 있어서, 토끼는 →, ↘, ↗ 방향으로만 이동한다. 토끼는 나가는 길에 최대한 많은 당근을 줍고싶다. 정문은 늑대 때문에 위험하므로 쪽문으로 나가야 하며, 토끼가 당근을 줍기 위해서는 그 당근이 있는 위치를 지나야 한다. 토끼가 어떤 쪽문에 도착했을때 반드시 그 문으로 탈출할 필요는 없으며, 더 움직여서 다른 쪽문으로 탈출해도 된다. 토끼는 얼마나 많은 당근을 주워갈 수 있을까? 토끼의 이동을 명확하게 정의..

>> 문제 바로가기 (https://www.acmicpc.net/problem/20047) 문제 100 원짜리 동전과 10 원짜리 동전이 임의의 순서로 한 선 위에 나열되어 있다고 하자. 이제 여기서 ‘두 손가락 이동’ 을 아래와 같이 정의하자. 단계 1: 임의의 두 동전을 선택한다. 단계 2: 단계 1 에서 선택한 두 동전을 둘의 순서를 유지한 채 임의의 위치로 이동한다. (두 동전 모두 제자리에 있거나 두 동전의 순서를 유지한다면 하나만 이동해도 된다.) ‘두 손가락 이동’ 후에도 다른 동전들 간의 순서는 그대로 유지된다. 예를 들어 100 원을 o, 10 원을 x 라 했을 때, 초기에 동전이 oxoxoxxxoo 와 같이 나열되어 있다 하자. 이제 이들 중 굵게 표시된 두 동전을 선택하여 두 손가락 ..

문제 프로젝트 하느라 바쁜 득수는 밥 먹을 시간이 부족하다. 그래서 주로 찾는 식당 네 개 중 하나에서 하루에 한 번 밥을 먹는다. 귀찮으면 굶을 때도 있다. 늘 새로운 느낌을 받고 싶었던 득수는 다음과 같은 규칙으로 다음날 갈 식당을 정한다. 첫날에는 굶거나, 임의로 원하는 식당 하나를 골라서 간다. 어제 굶지 않았다면, 오늘은 식당을 가지 않아도 된다. 어제 식당을 가지 않았다면, 오늘은 식당을 가서 밥을 먹어야 한다. 오늘 간 식당은 다음날 가지 않는다. 오늘 간 식당과 이웃한 식당은 다음날 가지 않는다. 만약 2번 식당을 오늘 갔다면, 다음날 1, 2, 3번 식당은 가지 않는다. 따라서 새로운 느낌을 받으려면 4번 식당을 가거나 굶어야 한다. 득수가 N일 치 식단표를 만들려고 한다. 위 규칙을 따..

문제 욱제는 구사과의 열렬한 팬이다. 오늘 욱제는 구사과에게 선물을 전달해주려고 한다. 지난 며칠간의 관찰 끝에 욱제는 구사과의 이동 패턴을 모두 파악했다. 구사과가 있는 곳은 N×M 크기의 직사각형 지도로 나타낼 수 있으며, 1×1크기의 정사각형으로 나누어져 있다. 구사과의 위치는 (i, j)로 나타낼 수 있으며, (i, j)는 위에서부터 i번째 칸, 왼쪽에서부터 j번째 칸을 의미한다. 지도의 각 칸에는 E, S, B중의 한 문자가 쓰여져 있는데, 구사과는 이 문자를 이용해서 이동한다. 구사과의 위치가 (i, j)인 경우에 E가 쓰여져 있는 칸에 서 있었다면 (i, j+1)로, S의 경우에는 (i+1, j)로, B의 경우에는 (i, j+1) 또는 (i+1, j)로 순간이동한다. 구사과는 지치지 않기 때..

문제 서기 2012년! 드디어 2년간 수많은 국민들을 기다리게 한 게임 ACM Craft (Association of Construction Manager Craft)가 발매되었다. 이 게임은 지금까지 나온 게임들과는 다르게 ACM크래프트는 다이나믹한 게임 진행을 위해 건물을 짓는 순서가 정해져 있지 않다. 즉, 첫 번째 게임과 두 번째 게임이 건물을 짓는 순서가 다를 수도 있다. 매 게임시작 시 건물을 짓는 순서가 주어진다. 또한 모든 건물은 각각 건설을 시작하여 완성이 될 때까지 Delay가 존재한다. 위의 예시를 보자. 이번 게임에서는 다음과 같이 건설 순서 규칙이 주어졌다. 1번 건물의 건설이 완료된다면 2번과 3번의 건설을 시작할수 있다. (동시에 진행이 가능하다) 그리고 4번 건물을 짓기 위해..