오구리의 DevLog

▶20444 - 색종이와 가위 ▶문제오늘도 역시 준성이는 어김없이 색종이와 쿼리를 푸는 데 실패하였다!!색종이에 열등감을 느낀 준성이는 가위로 눈에 보이는 색종이를 모두 잘라 버리려고 한다!!색종이를 자를 때는 다음과 같은 규칙을 따른다.색종이는 직사각형이며, 색종이를 자를 때는 한 변에 평행하게 자른다.자르기 시작했으면, 경로 상의 모든 색종이를 자를 때까지 멈추지 않는다.이미 자른 곳을 또 자를 수 없다.분노에 찬 가위질을 하던 준성이는 갑자기 하나의 색종이를 정확히 n번의 가위질로 k개의 색종이 조각으로 만들 수 있는지 궁금해졌다.궁금하지만 화가 나서 코딩에 집중할 수 없는 준성이 대신 코드를 작성해 주도록 하자. ▶입력첫 줄에 정수 n, k가 주어진다. (1 ≤ n ≤ 2^31-1, 1 ≤ k ≤..

▶15786 - Send me the money ▶문제석규는 해외로 저렴하고 간편하게 송금할 수 있는 센트비 서비스를 이용하여 CTP 왕국에 놀러간 형동이에게 돈을 보내주려고 한다. 하지만 안타깝게도 석규는 센트비 비밀번호를 까먹어버렸고 돈을 보내주지 못한다. 다행히도 석규는 평소에 포스트잇에 비밀번호를 적어놓는다. 비밀번호는 알파벳 대문자로만 구성이 되어있으며 석규는 이 중 일부를 정확히 기억하고 있다.석규는 포스트잇을 확인하여 비밀번호를 입력하려고 했지만, 포스트잇은 여러 장 존재했고 이 중 어떤 포스트잇이 센트비 비밀번호가 적힌 포스트잇인지 모른다.석규는 센트비 비밀번호의 알파벳 중 등장하는 순서대로 N글자만 정확히 기억하고 있으며 포스트잇 중에 이 순서를 갖는 포스트잇이 센트비 비밀번호일 가능성이..

▶24445 - 알고리즘 수업 - 너비 우선 탐색 2 ▶문제오늘도 서준이는 너비 우선 탐색(BFS) 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해 보자.N개의 정점과 M개의 간선으로 구성된 무방향 그래프(undirected graph)가 주어진다. 정점 번호는 1번부터 N번이고 모든 간선의 가중치는 1이다. 정점 R에서 시작하여 너비 우선 탐색으로 노드를 방문할 경우 노드의 방문 순서를 출력하자.너비 우선 탐색 의사 코드는 다음과 같다. 인접 정점은 내림차순으로 방문한다.bfs(V, E, R) { # V : 정점 집합, E : 간선 집합, R : 시작 정점  for each v ∈ V - {R}  visited[v]  ▶입력첫째 줄에 정점의 수..

▶25193 - 곰곰이의 식단 관리▶문제곰곰이는 치킨을 좋아한다. 그러다 보니 매 끼니에 치킨을 먹고 있다. 당신은 곰곰이의 트레이너로서 곰곰이의 식단을 관리해 주기로 했다.곰곰이가 N일간 먹어야 할 음식들의 리스트가 주어졌을 때, 리스트의 순서를 원하는 대로 조정하여 곰곰이가 연속으로 치킨을 먹는 날의 최댓값을 가장 작게 만들려고 한다.곰곰이의 건강을 위해 위와 같은 프로그램을 작성해 보자. ▶입력첫 번째 줄에 식단을 정할 일수 N(1≤N≤100000)이 주어진다.두 번째 줄에 음식의 리스트인 길이 N의 문자열 S가 주어진다. 문자열은 영어 대문자로만 이루어져 있다. Si가 C인 경우, i번째 음식이 치킨이며, 그 외의 경우에는 다른 음식이다. ▶출력첫째 줄에 모든 집을 칠하는 비용의 최솟값을 출력한다..