반응형 백준알고리즘/동적 계획법176 (Python/🥇4)백준알고리즘16432번: 떡장수와 호랑이 문제 바로가기 문제:떡장수 동희는 매일 새벽에 갓 만든 떡을 들고 산을 넘어 장터로 가서 떡을 팝니다. 동희가 만드는 떡의 종류는 1번부터 9번까지 있습니다. 산에는 동희가 나타나기를 기다렸다가 동희를 협박하여 떡을 하나 가져가는 호랑이가 살고 있습니다. 이 호랑이는 입맛이 까다로워 전날에 먹었던 떡과 같은 종류의 떡이면 먹지 않습니다. 만약 줄 수 있는 떡이 없다면 동희는 호랑이에게 잡아먹히고 맙니다. 동희는 N일 동안 떡을 팔러 매일 장터에 나가야 합니다. 동희가 만드는 떡들의 종류는 재료 공급 사정에 따라 종류가 매일 달라집니다. 동희가 N일 동안 호랑이에게 잡아먹히지 않도록 호랑이에게 줄 떡들을 골라주세요.입력:첫 번째 줄에 동희가 떡을 팔아야 할 날의 수 N이 (1 ≤ N ≤ 1,000) 이 주.. 2025. 7. 1. (Python/🥇1)백준알고리즘 2098번: 외판원 순회 문제 바로가기 문제:외판원 순회 문제는 영어로 Traveling Salesman problem (TSP) 라고 불리는 문제로 computer science 분야에서 가장 중요하게 취급되는 문제 중 하나이다. 여러 가지 변종 문제가 있으나, 여기서는 가장 일반적인 형태의 문제를 살펴보자. 1번부터 N번까지 번호가 매겨져 있는 도시들이 있고, 도시들 사이에는 길이 있다. (길이 없을 수도 있다) 이제 한 외판원이 어느 한 도시에서 출발해 N개의 도시를 모두 거쳐 다시 원래의 도시로 돌아오는 순회 여행 경로를 계획하려고 한다. 단, 한 번 갔던 도시로는 다시 갈 수 없다. (맨 마지막에 여행을 출발했던 도시로 돌아오는 것은 예외) 이런 여행 경로는 여러 가지가 있을 수 있는데, 가장 적은 비용을 들이.. 2024. 11. 4. (Python/🥇3)백준알고리즘 2186번: 문자판 문제 바로가기 문제:알파벳 대문자가 한 칸에 한 개씩 적혀있는 N×M 크기의 문자판이 있다. 편의상 모든 문자는 대문자라 생각하자. 예를 들어 아래와 같은 문자판을 보자.KAKTXEASYRWUZBQP이 문자판의 한 칸(아무 칸이나 상관없음)에서 시작하여 움직이면서, 그 칸에 적혀 있는 문자들을 차례대로 모으면 하나의 단어를 만들 수 있다. 움직일 때는 상하좌우로 K개의 칸까지만 이동할 수 있다. 예를 들어 K=2일 때 아래의 그림의 가운데에서는 'X' 표시된 곳으로 이동할 수 있다. X X XX XX X X 반드시 한 칸 이상 이동을 해야 하고, 같은 자리에 머물러 있을 수 없다. 또, 같은 칸을 여러 번 방문할 수 있다.이와 같은 문자판과 K, 그리고 하나의 영단어가 주어졌을 때, 이.. 2024. 11. 3. (Python/🥇3)백준알고리즘 2482번: 색상환 문제 바로가기 문제:색을 표현하는 기본 요소를 이용하여 표시할 수 있는 모든 색 중에서 대표적인 색을 고리 모양으로 연결하여 나타낸 것을 색상환이라고 한다. 미국의 화가 먼셀(Munsell)이 교육용으로 고안한 20색상환이 널리 알려져 있다. 아래 그림은 먼셀의 20색상환을 보여준다. 색상환에서 인접한 두 색은 비슷하여 언뜻 보면 구별하기 어렵다. 위 그림의 20색상환에서 다홍은 빨강과 인접하고 또 주황과도 인접하다. 풀색은 연두, 녹색과 인접하다. 시각적 대비 효과를 얻기 위하여 인접한 두 색을 동시에 사용하지 않기로 한다. 주어진 색상환에서 시각적 대비 효과를 얻기 위하여 서로 이웃하지 않은 색들을 선택하는 경우의 수를 생각해 보자. 먼셀의 20색상환에서 시각적 대비 효과를 얻을 수 있게 10개의 색.. 2024. 11. 1. (Python/플5)백준알고리즘 11375번 문제 바로가기 문제:박성원은 이 문제를 풀지 못했다. 서로 다른 정수로 이루어진 집합이 있다. 이 집합의 순열을 합치면 큰 정수 하나를 만들 수 있다. 예를 들어, {5221,40,1,58,9}로 5221401589를 만들 수 있다. 합친수가 정수 K로 나누어 떨어지는 순열을 구하는 프로그램을 작성하시오. 하지만, 박성원은 이 문제를 풀지 못했다. 따라서 박성원은 그냥 랜덤하게 순열 하나를 정답이라고 출력하려고 한다. 이 문제에는 정답이 여러 개 있을 수도 있고, 박성원이 우연히 문제의 정답을 맞출 수도 있다. 박성원이 우연히 정답을 맞출 확률을 분수로 출력하는 프로그램을 작성하시오.입력:첫째 줄에 집합의 수의 개수 N이 주어진다. N은 15보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 집합.. 2024. 10. 27. (Python/🥇3)백준알고리즘 1082번: 방 번호 문제 바로가기 문제:스타트링크가 입주한 사무실은 방 번호를 직접 정할 수 있다. 방 번호를 정하려면 1층 문방구에서 파는 숫자를 구매해야 한다. 숫자를 구매하기 위해 준비한 금액은 M원이다. 문방구에서 파는 숫자는 0부터 N-1까지이고, 각 숫자 i의 가격은 Pi이다. 문방구에서는 같은 숫자를 여러 개 구매할 수 있고, 문방구는 매우 많은 재고를 보유하고 있기 때문에, 항상 원하는 만큼 숫자를 구매할 수 있다. 방 번호가 0이 아니라면 0으로 시작할 수 없다. 예를 들어, N = 3, M = 21, P0 = 6, P1 = 7, P2 = 8이라면, 만들 수 있는 가장 큰 방 번호는 210이다. 최대 M원을 사용해서 만들 수 있는 가장 큰 방 번호를 구해보자.입력:첫째 줄에 N이 주아진다. 둘째 줄에는 공백.. 2024. 10. 12. 이전 1 2 3 4 ··· 13 다음 반응형
