공작소

>> 문제 바로가기 (https://www.acmicpc.net/problem/16943) 문제 두 정수 A와 B가 있을 때, A에 포함된 숫자의 순서를 섞어서 새로운 수 C를 만들려고 한다. 즉, C는 A의 순열 중 하나가 되어야 한다. 가능한 C 중에서 B보다 작으면서, 가장 큰 값을 구해보자. C는 0으로 시작하면 안 된다. 입력 첫째 줄에 두 정수 A와 B가 주어진다. 출력 B보다 작은 C중에서 가장 큰 값을 출력한다. 그러한 C가 없는 경우에는 -1을 출력한다. 풀이 과정 A에 포함된 숫자를 하나씩 사용하는 백트래킹을 구현한다. 비트마스킹을 통해 어느 숫자를 고르지 않았는지 판별했다. import sys input = sys.stdin.readline a, b = map(int, input()...

>> 문제 바로가기 (https://www.acmicpc.net/problem/2304) 문제 N 개의 막대 기둥이 일렬로 세워져 있다. 기둥들의 폭은 모두 1 m이며 높이는 다를 수 있다. 이 기둥들을 이용하여 양철로 된 창고를 제작하려고 한다. 창고에는 모든 기둥이 들어간다. 이 창고의 지붕을 다음과 같이 만든다. 지붕은 수평 부분과 수직 부분으로 구성되며, 모두 연결되어야 한다. 지붕의 수평 부분은 반드시 어떤 기둥의 윗면과 닿아야 한다. 지붕의 수직 부분은 반드시 어떤 기둥의 옆면과 닿아야 한다. 지붕의 가장자리는 땅에 닿아야 한다. 비가 올 때 물이 고이지 않도록 지붕의 어떤 부분도 오목하게 들어간 부분이 없어야 한다. 그림 1은 창고를 옆에서 본 모습을 그린 것이다. 이 그림에서 굵은 선으로 ..

>> 문제 바로가기 (https://www.acmicpc.net/problem/12845) 문제 영관이는 게임을 좋아한다. 별의별 게임을 다 하지만 그 중에서 제일 좋아하는 게임은 모두의 마블이다. 어김없이 오늘도 영관이는 학교 가는 버스에서 캐릭터 합성 이벤트를 참여했다. 이번 이벤트는 다음과 같다. 순서가 매겨진 여러 장의 카드가 있다. 각각의 카드는 저마다 레벨이 있다. 카드 A에 카드 B를 덧붙일 수 있다. 이때 붙이는 조건은 다음과 같다. 두 카드는 인접한 카드여야 한다. 업그레이드 된 카드 A의 레벨은 변하지 않는다. 카드 합성을 할 때마다 두 카드 레벨의 합만큼 골드를 받는다. 영관이가 골드를 최대한 많이 받을 수 있게 여러분이 도와주자. 예를 들어, c1, c2, c3로 연속된 카드 3개가..

>> 문제 바로가기 (https://www.acmicpc.net/problem/17472) 문제 섬으로 이루어진 나라가 있고, 모든 섬을 다리로 연결하려고 한다. 이 나라의 지도는 N×M 크기의 이차원 격자로 나타낼 수 있고, 격자의 각 칸은 땅이거나 바다이다. 섬은 연결된 땅이 상하좌우로 붙어있는 덩어리를 말하고, 아래 그림은 네 개의 섬으로 이루어진 나라이다. 색칠되어있는 칸은 땅이다. 다리는 바다에만 건설할 수 있고, 다리의 길이는 다리가 격자에서 차지하는 칸의 수이다. 다리를 연결해서 모든 섬을 연결하려고 한다. 섬 A에서 다리를 통해 섬 B로 갈 수 있을 때, 섬 A와 B를 연결되었다고 한다. 다리의 양 끝은 섬과 인접한 바다 위에 있어야 하고, 한 다리의 방향이 중간에 바뀌면 안된다. 또, 다..

>> 문제 바로가기 (https://www.acmicpc.net/problem/14725) 문제 개미는(뚠뚠) 오늘도(뚠뚠) 열심히(뚠뚠) 일을 하네. 개미는 아무말도 하지 않지만 땀을 뻘뻘 흘리면서 매일 매일을 살길 위해서 열심히 일을 하네. 한 치 앞도(뚠뚠) 모르는(뚠뚠) 험한 이 세상(뚠뚠) 그렇지만(뚠뚠) 오늘도 행복한 개미들! 우리의 천재 공학자 윤수는 이 개미들이 왜 행복한지 궁금해졌다. 행복의 비결이 개미가 사는 개미굴에 있다고 생각한 윤수는 개미굴의 구조를 알아보기 위해 로봇 개미를 만들었다. 로봇 개미는 센서가 있어 개미굴의 각 층에 먹이가 있는 방을 따라 내려가다 더 이상 내려갈 수 없으면 그 자리에서 움직이지 않고 신호를 보낸다. 이 신호로 로봇 개미는 개미굴 각 층을 따라 내려오면..

>> 문제 바로가기 (https://www.acmicpc.net/problem/14675) 문제 그래프 이론에서 단절점(cut vertex)과 단절선(bridge)은 다음과 같이 정의 된다. 단절점(cut vertex) : 해당 정점을 제거하였을 때, 그 정점이 포함된 그래프가 2개 이상으로 나뉘는 경우, 이 정점을 단절점이라 한다. 단절선(bridge) : 해당 간선을 제거하였을 때, 그 간선이 포함된 그래프가 2개 이상으로 나뉘는 경우, 이 간선을 단절선이라 한다. 이 단절점과 단절선을 우리는 트리(tree)에서 구하려고 한다. 그래프 이론에서 트리(tree)의 정의는 다음과 같다. 트리(tree) : 사이클이 존재하지 않으며, 모든 정점이 연결되어 있는 그래프 트리의 정보와 질의가 주어질 때, 질의..