공작소

>> 문제 바로가기 (https://www.acmicpc.net/problem/23324) 문제 연두는 방금 "플로이드 와샬 알고리즘"을 공부했다. 이 알고리즘은 N개의 정점으로 이루어진 그래프에서, 모든 정점 쌍의 최단 거리를 O(N^3)에 구해준다. 신이 난 연두는 자신이 좋아하는 그래프를 하나 가져왔다. 이 그래프는 N개의 정점과 M개의 양방향 간선으로 이루어진 단순 연결 그래프이며, 정점에는 1,2,…,n으로 번호가 매겨져있다. 또한 딱 하나의 간선에만 1의 가중치가 있고 나머지 간선은 가중치가 0이다. 이제 이 그래프에서 모든 정점 쌍의 최단 거리의 합을 구해보려고 한다. 즉, 1 ≤ i < j ≤ N를 만족하는 모든 N(N−1)/2개의 쌍 (i,j)에 대해, i번 정점과 j번 정점간의 최단거리..

>> 문제 바로가기 (https://www.acmicpc.net/problem/16927) 문제 크기가 N×M인 배열이 있을 때, 배열을 돌려보려고 한다. 배열은 다음과 같이 반시계 방향으로 돌려야 한다. A[1][1] ← A[1][2] ← A[1][3] ← A[1][4] ← A[1][5] ↓ ↑ A[2][1] A[2][2] ← A[2][3] ← A[2][4] A[2][5] ↓ ↓ ↑ ↑ A[3][1] A[3][2] → A[3][3] → A[3][4] A[3][5] ↓ ↑ A[4][1] → A[4][2] → A[4][3] → A[4][4] → A[4][5] 예를 들어, 아래와 같은 배열을 2번 회전시키면 다음과 같이 변하게 된다. 1 2 3 4 2 3 4 8 3 4 8 6 5 6 7 8 1 7 7 6 2..

>> 문제 바로가기 (https://www.acmicpc.net/problem/16926) 문제 크기가 N×M인 배열이 있을 때, 배열을 돌려보려고 한다. 배열은 다음과 같이 반시계 방향으로 돌려야 한다. A[1][1] ← A[1][2] ← A[1][3] ← A[1][4] ← A[1][5] ↓ ↑ A[2][1] A[2][2] ← A[2][3] ← A[2][4] A[2][5] ↓ ↓ ↑ ↑ A[3][1] A[3][2] → A[3][3] → A[3][4] A[3][5] ↓ ↑ A[4][1] → A[4][2] → A[4][3] → A[4][4] → A[4][5] 예를 들어, 아래와 같은 배열을 2번 회전시키면 다음과 같이 변하게 된다. 1 2 3 4 2 3 4 8 3 4 8 6 5 6 7 8 1 7 7 6 2..

>> 문제 바로가기 (https://www.acmicpc.net/problem/1946) 문제 언제나 최고만을 지향하는 굴지의 대기업 진영 주식회사가 신규 사원 채용을 실시한다. 인재 선발 시험은 1차 서류심사와 2차 면접시험으로 이루어진다. 최고만을 지향한다는 기업의 이념에 따라 그들은 최고의 인재들만을 사원으로 선발하고 싶어 한다. 그래서 진영 주식회사는, 다른 모든 지원자와 비교했을 때 서류심사 성적과 면접시험 성적 중 적어도 하나가 다른 지원자보다 떨어지지 않는 자만 선발한다는 원칙을 세웠다. 즉, 어떤 지원자 A의 성적이 다른 어떤 지원자 B의 성적에 비해 서류 심사 결과와 면접 성적이 모두 떨어진다면 A는 결코 선발되지 않는다. 이러한 조건을 만족시키면서, 진영 주식회사가 이번 신규 사원 채용..

>> 문제 바로가기 (https://www.acmicpc.net/problem/24523) 풀이 과정 i번째 수 의 뒤에 나오는 i+1 번째 수가 i번째 수와 같은 수가 아니라면 무조건 i+1이 최솟값 j이다. 같은 수가 연속으로 여러 번 나오다가 다른 수가 나온다면, 다르게 나온 수 앞에 있는 모든 수들의 j 는 해당 다르게 나온 수의 인덱스가 된다. 같은 수가 연속으로 나오는 횟수를 카운팅했다가, 다른 수가 나왔을 때 카운트한만큼 현재 인덱스를 출력하고, 수열의 끝까지 찾았는데도 만족하는 j 가 없는 수들은 -1 을 출력하도록 구현한다. import sys input = sys.stdin.readline n = int(input().rstrip()) arr = list(map(int, input()...

>> 문제 바로가기 (https://www.acmicpc.net/problem/16507) 문제 호근이는 겁이 많아 어두운 것을 싫어한다. 호근이에게 어떤 사진을 보여주려는데 사진의 밝기가 평균 이상이 되지 않으면 일절 보려 하지 않는다. 호근이가 이 사진에서 일부분이라도 볼 수 있는 부분을 찾아주자. 위 그림은 호근이에게 보여줄 5×6 크기의 사진이며, 각 픽셀은 밝기를 나타낸다. 호근이가 사진의 일부분이라도 볼 수 있는지 알아보기 위해서는 두 점 (r1, c1)과 (r2, c2)를 꼭짓점으로 하는 직사각형의 밝기 평균을 구해야 한다. 예를 들어, 위 그림에서는 (2, 2)와 (4, 5)를 꼭짓점으로 하는 직사각형을 말한다. 호근이에게 보여줄 R×C 크기의 사진이 주어질 때, 사진의 일부분에 해당하는 ..

>> 문제 바로가기 (https://www.acmicpc.net/problem/11051) 풀이 과정 import sys import math input = sys.stdin.readline n, k = map(int, input().rstrip().split()) print(math.comb(n, k)%10007) 파이썬은 math.comb 를 사용해도 되지만... 이 문제가 실버 2인 이유가 있으므로 다른 방식으로도 풀이해보자. 해당 문제는 파스칼의 삼각형 모양을 떠올리면 쉽게 풀이할 수 있다. 파스칼의 삼각형은 바로 위의 왼쪽 수와 오른쪽 수를 더한 값이므로, 이를 DP 점화식으로 활용하여 풀이한다. import sys input = sys.stdin.readline n, k = map(int, i..

>> 문제 바로가기 (https://www.acmicpc.net/problem/18429) 문제 웨이트 트레이닝을 좋아하는 어떤 대학원생은, 현재 3대 운동 중량 500의 괴력을 소유하고 있다. 다만, 하루가 지날 때마다 중량이 K만큼 감소한다. 예를 들어 K=4일 때, 3일이 지나면 중량이 488로 감소하게 된다. 따라서 운동을 하지 않고, 가만히 있다면 매일매일 중량이 감소할 뿐이다. 다행히도 이 대학원생은 N개의 서로 다른 운동 키트를 가지고 있다. 이 대학원생은 하루에 1개씩의 키트를 사용하며, 매일 어떤 키트를 사용할 지는 마음대로 결정할 수 있다. 운동 키트들은 각각의 중량 증가량을 가지고 있으며, 사용할 때마다 즉시 중량이 증가하게 된다. 이 때 몇몇 운동 키트들의 중량 증가량이 같을 수 있..

>> 문제 바로가기 (https://www.acmicpc.net/problem/19940) 문제 피자를 굽는 전자식 오븐이 있다. 이 오븐에 재료는 넣고 정확히 N분 동안 동작을 시키고자 한다. 그런데 이 오븐에 준비된 버튼은 아래와 같은 동작을 하는 5가지이다. 즉, 각각의 버튼은 동작 시간을 추가시키거나 감소시킨다. 처음에 피자 오븐의 첫 시간은 0분으로 정해져 있다. 시간을 감소시키는 버튼을 눌러서 시간이 0분보다 작아지는 경우에는 0분으로 설정된다. t가 현재 오븐에 세팅된 시간, t'은 버튼을 누른 뒤의 시간을 의미할 때, 각 버튼은 다음과 같은 기능을 가지고 있다. ADDH: t' = t + 60 ADDT: t' = t + 10 MINT: t' = t - 10 ADDO: t' = t + 1 M..

>> 문제 바로가기 (https://www.acmicpc.net/problem/1522) 문제 a와 b로만 이루어진 문자열이 주어질 때, a를 모두 연속으로 만들기 위해서 필요한 교환의 회수를 최소로 하는 프로그램을 작성하시오. 이 문자열은 원형이기 때문에, 처음과 끝은 서로 인접해 있는 것이다. 예를 들어, aabbaaabaaba이 주어졌을 때, 2번의 교환이면 a를 모두 연속으로 만들 수 있다. 입력 첫째 줄에 문자열이 주어진다. 문자열의 길이는 최대 1,000이다. 출력 첫째 줄에 필요한 교환의 회수의 최솟값을 출력한다. 풀이 과정 a를 모두 연속으로 만들기 위해선, b도 연속으로 만들어야 a도 연속이다. (aaabbb, baaaab, bbbbaab) 즉 b를 전부 붙여야 하므로, b의 전체 갯수만..