기록

문제 https://www.acmicpc.net/problem/15661 15661번: 링크와 스타트 첫째 줄에 N(4 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에 S가 주어진다. 각 줄은 N개의 수로 이루어져 있고, i번 줄의 j번째 수는 Sij 이다. Sii는 항상 0이고, 나머지 Sij는 1보다 크거나 같고, 100 www.acmicpc.net 풀이 1. make team 팀1이 가질수 있는 선수들의 경우의 수를 구한다. 선수의 수를 n//2로 둔 이유는 중복을 제거하기 위해서이다. (아래 두 경우를 같게 취급) team1 team1 team1 team2 team1 team1 team2 team2 team2 team2 team1 team2 team2 team1 2. calculation ..

문제 https://www.acmicpc.net/problem/10830 10830번: 행렬 제곱 크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다. www.acmicpc.net 풀이 1) 분할 정복을 이용한 거듭제곱 number을 n번 곱한다고 하면, 아래처럼 적을 수 있다. 이를 행렬에도 적용하면, 문제를 해결할 수 있다. def power(number, n) : if n==0 : return 1 elif n이 짝수 : return power(number², n//2) elif n이 홀수 : return number*power(number², n//2) 문제에서는 n의 최대값을..

문제 https://www.acmicpc.net/problem/2961 2961번: 도영이가 만든 맛있는 음식 첫째 줄에 재료의 개수 N(1 ≤ N ≤ 10)이 주어진다. 다음 N개 줄에는 그 재료의 신맛과 쓴맛이 공백으로 구분되어 주어진다. 모든 재료를 사용해서 요리를 만들었을 때, 그 요리의 신맛과 쓴맛은 www.acmicpc.net 풀이 1) dfs 해당 음식을 사용할 때와 사용하지 않을 때를 나누어서, 모든 경우를 탐색한다. 코드 import sys sys.setrecursionlimit(10**6) N = int(input()) arr = [list(map(int, input().split())) for i in range(N)] def dfs(p, sour, bitter) : if p+1>=l..

문제 1022번: 소용돌이 예쁘게 출력하기 첫째 줄에 네 정수 r1, c1, r2, c2가 주어진다. www.acmicpc.net 풀이 board의 내부의 점 (r, c)가 주어질 때, board[r][c]에 적어야 할 값을 반환하는 함수 f가 있다고 하자. ex) f(-3, -3) = 37 f(0, 1) =2 1) 어느 그룹에 속하는가? 메인그룹 mg = abs(max(r, c, key = abs)) 안쪽에서 바깥쪽 껍데기로 나오면서 0, 1, 2... 그룹으로 묶을 수 있다. 0그룹 : 1 1그룹 : 2~9 2그룹 : 10~25 ... 점A (-2, 3)이 주어졌다고 할때 점 A는 3그룹에 속한다. 서브그룹 # corner일때 if abs(r)==abs(c) : if c>0 and r

문제 https://www.acmicpc.net/problem/2208 2208번: 보석 줍기 화영이는 고대 유적을 탐사하던 도중 보석을 발견했다. 유적 속에는 N(1 ≤ N ≤ 100,000)개의 보석들이 일렬로 놓여 있었다. 각각의 보석의 가치는 다를 수 있기 때문에, 화영이는 가급적 많은 이득 www.acmicpc.net 풀이 1) 연속 누적합 dp 우선, 보석의 개수를 신경쓰지 않고, 연속해서 얻을 수 있는 보석의 누적 가치합을 구한다. 이를 위해 세가지 경우를 고려한다. 이전 보석과 연속해서 줍는다. 이전 보석을 버리고, 현재 보석만을 줍는다. 아무 보석도 줍지 않는다. 2) M개 이상의 보석을 줍는다. prefix_sum 2-1. 현재 위치를 포함해서, 왼쪽으로 이동하면서 M개의 보석을 줍는다..

문제 https://www.acmicpc.net/problem/20040 20040번: 사이클 게임 사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n − 1 까지 고유한 www.acmicpc.net 풀이 분리집합 이미 같은 집합에 있는 원소(부모가 같은 원소)들이 언급되었다면, 사이클이 생긴 것이다. 코드 def find(n) : if parent[n]==n : return n parent[n] = find(parent[n]) return parent[n] def union(x, y) : x = find(x) y = find(y) if x

문제 https://www.acmicpc.net/problem/12100 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net 풀이 1) DFS def dfs(board, w) : if w>=5 : return max(max(board, key = max)) return max(solve(up(board), w+1), solve(down(board), w+1), solve(right(board), w+1), solve(left(board), w+1)) 2) 블록 오른쪽으로 밀기 각 행을 ..

문제 https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net https://www.acmicpc.net/problem/12015 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net h..