본문 바로가기

숨막히는 알고말고

 (211)
[Baekjoon] 순열 사이클(BOJ 10451) 👀 문제 설명 문제 1부터 N까지 정수 N개로 이루어진 순열을 나타내는 방법은 여러 가지가 있다. 예를 들어, 8개의 수로 이루어진 순열 (3, 2, 7, 8, 1, 4, 5, 6)을 배열을 이용해 표현하면 와 같다. 또는, Figure 1과 같이 방향 그래프로 나타낼 수도 있다. 순열을 배열을 이용해 로 나타냈다면, i에서 πi로 간선을 이어 그래프로 만들 수 있다. Figure 1에 나와있는 것 처럼, 순열 그래프 (3, 2, 7, 8, 1, 4, 5, 6) 에는 총 3개의 사이클이 있다. 이러한 사이클을 "순열 사이클" 이라고 한다. N개의 정수로 이루어진 순열이 주어졌을 때, 순열 사이클의 개수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스..
[Baekjoon] 홍준 프로그래밍 대회(BOJ 1222) 👀 문제 설명 문제 홍준이는 프로그래밍 대회를 개최했다. 이 대회는 사람들이 팀을 이루어서 참가해야 하며, 팀원의 수는 홍준이가 정해준다. 팀원이 홍준이가 정한 값보다 부족하다면, 그 팀은 대회에 참여할 수 없다. 모든 팀은 같은 수의 팀원으로 이루어져 있다. 대회에 참여 의사를 밝힌 학교는 총 N개이다. 각 학교는 모든 학생이 참여할 수 있는 경우에만 대회에 참가한다. 즉, 남는 사람 없이 모든 학생이 팀에 들어갈 수 있어야 한다. 대회는 예선과 본선으로 구성되어 있다. 모든 팀은 같은 학교 소속으로 이루어져 있어야 한다. 예선에서 각 학교 1등팀만 본선에 진출한다. 홍준이의 대회는 올해가 첫 해이기 때문에, 많은 관심이 필요하다. 따라서, 본선에 참가하는 사람의 수를 최대가 되도록 팀원의 수를 정하려..
[Baekjoon] 추월(BOJ 2002) 👀 문제 설명 문제 대한민국을 비롯한 대부분의 나라에서는 터널 내에서의 차선 변경을 법률로 금하고 있다. 조금만 관찰력이 있는 학생이라면 터널 내부에서는 차선이 파선이 아닌 실선으로 되어 있다는 것을 알고 있을 것이다. 이는 차선을 변경할 수 없음을 말하는 것이고, 따라서 터널 내부에서의 추월은 불가능하다. 소문난 명콤비 경찰 대근이와 영식이가 추월하는 차량을 잡기 위해 한 터널에 투입되었다. 대근이는 터널의 입구에, 영식이는 터널의 출구에 각각 잠복하고, 대근이는 차가 터널에 들어가는 순서대로, 영식이는 차가 터널에서 나오는 순서대로 각각 차량 번호를 적어 두었다. N개의 차량이 지나간 후, 대근이와 영식이는 자신들이 적어 둔 차량 번호의 목록을 보고, 터널 내부에서 반드시 추월을 했을 것으로 여겨지는..
[Baekjoon] 기상개스터(BOJ 10709) 👀 문제 설명 문제 JOI시는 남북방향이 H 킬로미터, 동서방향이 W 킬로미터인 직사각형 모양이다. JOI시는 가로와 세로의 길이가 1킬로미터인 H × W 개의 작은 구역들로 나뉘어 있다. 북쪽으로부터 i 번째, 서쪽으로부터 j 번째에 있는 구역을 (i, j) 로 표시한다. 각 구역의 하늘에는 구름이 있을 수도, 없을 수도 있다. 모든 구름은 1분이 지날 때마다 1킬로미터씩 동쪽으로 이동한다. 오늘은 날씨가 정말 좋기 때문에 JOI시의 외부에서 구름이 이동해 오는 경우는 없다. 지금 각 구역의 하늘에 구름이 있는지 없는지를 알고 있다. 기상청에서 일하고 있는 여러분은 각 구역에 대해서 지금부터 몇 분뒤 처음으로 하늘에 구름이 오는지를 예측하는 일을 맡았다. 각 구역에 대해서 지금부터 몇 분뒤 처음으로 하..
[Baekjoon] 피보나치 수의 확장(BOJ 1788) 👀 문제 설명 문제 수학에서, 피보나치 수는 위의 점화식과 같이 귀납적으로 정의되는 수열이다. 위의 식에서도 알 수 있듯이, 피보나치 수 F(n)은 0 이상의 n에 대해서만 정의된다. 하지만 피보나치 수 F(n)을 n이 음수인 경우로도 확장시킬 수 있다. 위의 식에서 n>1인 경우에만 성립하는 F(n)=F(n-1)+F(n-2)를 n 0) // 양수일 때 return fibonacci[n]; else // 음수일 때 { if (n % 2 == 0) // 2로 나누어 떨어질 때 (절대값이 짝수일 때) return fibonacci[n * (-1)] * (-1); else // 2로 나누어 떨어지지 않을 때 (절대값이 홀수일 때) return fibonacci[n * (-1)]; } } int main() {..
[Baekjoon] 정상회담 2(BOJ 1670) 👀 문제 설명 문제 여러 개의 소국가로 나뉘어져 있었던 A국을 다시 하나의 국가로 합치기 위해 각 소국가의 대표 N명이 원탁에 모였다. 각 대표는 미리 원탁의 자리를 배정받았다. 회의를 시작하기 전에 일단 서로 악수를 하려고 한다. 각 대표는 한 사람과만 악수할수 있고, 모든 악수는 동시에 일어난다. 이때, 어떤 사람의 팔도 교차하지 않았을 때 완벽하게 악수했다고 한다. N이 주어지면 완벽하게 악수하는 경우의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 정상 회담에 참가한 사람의 수 N이 주어진다. 이 값은 10,000보다 작거나 같은 짝수이다. 출력 완벽한 악수의 경우의 수를 987654321로 나눈 나머지를 출력한다. 예제 입력 1 4 예제 출력 1 2 힌트 ✍🏻풀이 분류가 수학이라 수학으로 ..
[Baekjoon] 토너먼트(BOJ 1057) 👀 문제 설명 문제 김지민은 N명이 참가하는 스타 토너먼트에 진출했다. 토너먼트는 다음과 같이 진행된다. 일단 N명의 참가자는 번호가 1번부터 N번까지 배정받는다. 그러고 난 후에 서로 인접한 번호끼리 스타를 한다. 이긴 사람은 다음 라운드에 진출하고, 진 사람은 그 라운드에서 떨어진다. 만약 그 라운드의 참가자가 홀수명이라면, 마지막 번호를 가진 참가자는 다음 라운드로 자동 진출한다. 다음 라운드에선 다시 참가자의 번호를 1번부터 매긴다. 이때, 번호를 매기는 순서는 처음 번호의 순서를 유지하면서 1번부터 매긴다. 이 말은 1번과 2번이 스타를 해서 1번이 진출하고, 3번과 4번이 스타를 해서 4번이 진출했다면, 4번은 다음 라운드에서 번호 2번을 배정받는다. 번호를 다시 배정받은 후에 한 명만 남을 ..
[Baekjoon] 약수(BOJ 1037) 👀 문제 설명 문제 양수 A가 N의 진짜 약수가 되려면, N이 A의 배수이고, A가 1과 N이 아니어야 한다. 어떤 수 N의 진짜 약수가 모두 주어질 때, N을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N의 진짜 약수의 개수가 주어진다. 이 개수는 50보다 작거나 같은 자연수이다. 둘째 줄에는 N의 진짜 약수가 주어진다. 1,000,000보다 작거나 같고, 2보다 크거나 같은 자연수이고, 중복되지 않는다. 출력 첫째 줄에 N을 출력한다. N은 항상 32비트 부호있는 정수로 표현할 수 있다. 예제 입력 1 2 4 2 예제 출력 1 8 ✍🏻풀이 진짜 약수의 개수가 홀수일 때와 짝수일 때로 나눠서 생각했다. 1) 홀수일 때 정가운데 수를 가져와서 제곱하면 N이 나온다. 2) 짝수일 때 가운데 두 수를 가..

티스토리툴바