We will find a way, we always have.

-interstellar

Problem Solving 106

[코드포스] 1872 D. Plus Minus Permutation

📖 Solution 문제의 요구사항을 정리해보면 길이 n의 조합중에서 x배수의 숫자의 합에서 y배수의 숫자의 합의 차를 가장 크게 만들 수 있는 조합을 찾고 그 차를 출력하는 문제이다. A - B의 차를 크게 만들기 위해서는 A를 최대한 크게, B를 최대한 작게 만들면 된다. 그렇다면 x의 배수 위치에는 n부터 내림차순으로 배치하고, y의 배수 위치에는 1부터 오름차순으로 배치하면 된다. 둘이 겹치는 부분이 있을 수 있는데 이는 0이 되기 때문에 상관없다. 그렇다면 이제 구해야 하는 점은 n에서 x 배수의 갯수, y 배수의 갯수 그리고 겹치는 부분이다. 이 겹치는 부분은 lcm 을 사용하여 찾을 수 있다. 💻 Code HTML 삽입 미리보기할 수 없는 소스 🔗 Problem https://codeforc..

[백준] 20560번: 맛집 탐방

🔈 문제 은수는 맛집을 탐방하러 도시로 여행을 떠날 것이다. 은수가 갈 도시에는 총 $N$개의 맛집이 있다. 도시에는 맛집에서 맛집으로 이동할 수 있는 일방통행 길이 $M$개 있고, 각 길의 중간에는 기념품 상점이 있다. 어떤 길은 출발하는 맛집과 도착하는 맛집이 같을 수도 있으며, 여러 길이 같은 맛집을 연결할 수도 있다. 은수는 도시의 맛집에서 여행을 시작해서, 길을 이용해 맛집을 탐방하다 도시의 맛집에서 여행을 끝낼 것이다. 여행을 시작한 곳과 여행을 끝낸 곳이 같을 필요는 없다. 도시는 은수가 사는 마을에서 멀리 떨어져 있기 때문에, 은수는 한 번의 여행에서 최대한 많은 맛집과 상점을 들르려고 한다. 특히, 여행 중에 모든 맛집을 방문하거나 모든 기념품 상점을 방문한다면 다음 여행에서 할인 혜택을..

[백준] 1185: 유럽 여행

🔈 문제 민식이는 여름에 유럽여행을 떠날 계획이다. 방문할 나라는 총 N개의 나라이고 편리하게 1번부터 N번까지 번호를 붙였다. 또한 이 나라들 사이에 이동 가능한 길은 M개가 있는데 민식이는 귀찮기 때문에 N개의 나라가 서로 연결된 것을 유지시키면서 최대한 많은 길을 지도에서 제거하고자 한다. 즉, N-1개의 길만을 남겨야할 것이다. 각 길을 통과하기 위한 비용이 각기 다르고 한 나라를 도착하면 내야할 비용 역시 나라마다 다르게 정해져있다. 민식이는 모든 도시를 최소 한번 이상 방문하면서 최소 비용이 드는 방법을 찾고 있다. 물론 길과 나라는 여러 번 방문할 수 있고, 첫 시작 나라는 민식이가 정할 수 있고, 마지막 나라는 시작 나라이어야 한다. 이러한 민식이의 유럽 계획을 도와주자. 📝입력 첫 줄에는..

[구름톤 챌린지] 완벽한 햄버거 만들기 - 학습 일기 (1-4)

🔈 문제 문제의 요구사항은 N개의 정수 데이터가 주어졌을 때, 조건대로 정렬되어 있는지 확인하는 문제입니다. 여기서 주어진 조건은 배열의 최대값을 기준으로 왼쪽이나 오른쪽으로 갈수록 정수의 값이 같거나 감소해야 한다. 📚 문제 풀이 문제의 조건을 만족하려면 오름차순, 내림차순 혹은 올라갔다 내려가도록 정렬되어있는지 파악하면 된다. 조건을 만족하려면 배열안에 nums[i] > nums[i+1] < nums[i+2] 이 True 인 곳이 없어야 한다. 감소하다가 증가하는 값이 존재하면 안되기 때문이다. 반복문을 사용해 해당 값을 포함하고 있는지 아닌지 bool 값을 반환하여 문제를 해결할 수 있다. 모든 조건문이 참이면 참을 반환하는 all() 을 사용하여 문제를 해결하였다. 💻 코드 HTML 삽입 미리보기..

Problem Solving 2023.08.18

[백준] 28457번: Every? Only One's Marble - 파이썬

🔈 문제 유틸은 오늘도 혼자 집에 있다. 심심해서 같이 부루마불 게임을 할 사람을 찾아봤지만 아무도 없었다. 그렇게 한 시간, 두 시간... 도저히 참을 수 없었던 유틸은 부루마불 게임을 혼자 할 방법을 생각해 냈다. 혼자 하는 부루마불 게임에 적용되는 규칙은 다음과 같다. 일반 칸은 두 종류다. 도시 칸: 돈을 내고 땅을 사야 하는 칸 황금 열쇠 칸: 특정한 효과가 있는 카드가 발동되는 칸 특수 칸은 네 종류다. 시작 칸: 이 칸에 정확히 멈추거나 지나가게 되면, 월급을 받게 된다. 무인도 칸: 이 칸에 정확히 멈추게 되면, 다음 세 턴 동안 갇히게 된다. 갇혀 있는 동안, 두 주사위를 던졌을 때 눈이 같은 수로 나오면 무인도를 탈출하게 되며 두 주사위를 한 번 더 던져서 나온 수만큼 이동한다. 사회복..

[백준] 17132번: 두더지가 정보섬에 올라온 이유 - 파이썬

🔈 문제 두더지가 정보섬에 올라왔다! 두더지는 정보섬 지하에 여러 채의 자택을 소유하고 있다. 두더지는 집 사이를 오가는 걸 좋아한다. 정보섬에는 총 N개의 두더지 집이 있으며 이 집들은 N-1개의 길로 연결되어 있다. 임의의 집에서 또 다른 집으로 가는 경로는 항상 유일하게 하나만 존재한다. 즉, 두더지 집들은 트리 형태로 모두 연결되어 있다. 어떤 길을 지날 때, 두더지는 W만큼의 만족도를 얻는다. 어느 날, 아래의 그림과 같은 집을 가진 두더지는 집1에서 집4로 이동했다. 이때 거치게 되는 집은 (1 → 2 → 3 → 4)이다. 두더지는 한 번 이동할 때마다, 이동경로에 포함되는 만족도들 중에서 가장 최소인 만족도를 얻는다. 즉, (1 → 4)의 경우에는 만족도를 2만큼, (6 → 2)의 경우에는 ..

[백준] 2637번: 장난감 조립 - 파이썬

🔈 문제 우리는 어떤 장난감을 여러 가지 부품으로 조립하여 만들려고 한다. 이 장난감을 만드는데는 기본 부품과 그 기본 부품으로 조립하여 만든 중간 부품이 사용된다. 기본 부품은 다른 부품을 사용하여 조립될 수 없는 부품이다. 중간 부품은 또 다른 중간 부품이나 기본 부품을 이용하여 만들어지는 부품이다. 예를 들어보자. 기본 부품으로서 1, 2, 3, 4가 있다. 중간 부품 5는 2개의 기본 부품 1과 2개의 기본 부품 2로 만들어진다. 그리고 중간 부품 6은 2개의 중간 부품 5, 3개의 기본 부품 3과 4개의 기본 부품 4로 만들어진다. 마지막으로 장난감 완제품 7은 2개의 중간 부품 5, 3개의 중간 부품 6과 5개의 기본 부품 4로 만들어진다. 이런 경우에 장난감 완제품 7을 만드는데 필요한 기본..

[백준] 17398번: 통신망 분할

🔈 문제 BOJ의 인기스타, 방송인 권욱제는 통신 회사에 취업했다. 현재 이 통신 회사는 너무나 큰 통신망을 한 지사에서 관리하느라 큰 비용을 지불하고 있었다. 그래서 회사는 최근 IT의 트렌드 중 하나인 '탈중앙화'에 편승하여, 통신망을 분할하도록 결정했다. 그래서 욱제한테 통신망을 분할 할때 발생하는 비용을 분석하도록 지시했다. 현재 회사 망에는 1번부터 N번까지 총 N개의 통신 탑이 존재하며, 통신탑 간의 연결이 M개 존재한다. 이때 회사에서는 총 Q번 통신탑 간의 연결을 제거함으로써 하나의 통신망을 여러 개의 통신망으로 분리하려고 한다. 통신망이란, 통신탑의 연결을 통해 도달 가능한 통신탑들의 집합이다. 통신탑 간의 연결 관계를 제거할 때 드는 비용은 제거한 후 통신망이 두 개로 나누어진다면 나눠..

[백준] 백준 랜덤 디펜스

백준 랜덤 디펜스를 하는 방법을 알아보자! 백준 랜덤디펜스는 랜덤으로 한문제 뽑아서 문제를 푸는 것이다알고리즘 개념들을 어느 정도 익히면 이제 알고리즘 태그는 끄고 랜덤으로 문제를 푸는 연습도 해야한다. 실제 코딩테스트에서는 태그를 알려주지 않는다!!! 이전에 있던 백준 랜덤디펜스 사이트가 사라졌는데 solve.ac를 이용하는 방법이 있다!   solve.ac 메인 화면 중앙상단에 검색창이 있는데 이 친구를 사용한다. 다양한 검색 옵션을 제공하는데 예를 들어 골랜디(골드 랜덤 디펜스) 를 하고싶다면 아래와 같이 입력하고 alt + Enter 를 누르면 된다. 12345678내가&nbsp;풀지&nbsp;않은&nbsp;골드*g&nbsp;!@$me&nbsp;&nbsp;내가&nbsp;풀지&nbsp;않은&nbsp..