해킹왕 양선규

분할 정복 문제이다. N * N 형태의 좌석과 추첨번호가 주어진다.여기서 N은 2의 0승 ~ 2의 10승 중 하나이고, 따라서 정사각형 형태이며 4등분으로 분할이 가능하다. 특별상은 딱 한명만 받을 수 있다.사람이 1명밖에 없다면 그 사람이 수상한다.사람이 4명이라면(N : 2) 4명 중 추첨번호가 2번째로 작은 사람이 수상한다.사람이 16명(N : 4) 이상이라면, 각 구역에 사람이 4명만 남을 때까지 4등분한 후, 각 구역마다 2번째로 작은 사람을 가려내고, 그렇게 추려진 사람들 중에서 또 2번째로 작은 사람을 가려내고.. 하는 형태로 진행한다.  위 그림에선 왼쪽 위 : 1 , 오른쪽 위 : 3, 왼쪽 아래 : 5, 오른쪽 아래 : 7 이다.이렇게 추첨된 1, 3, 5, 7 중에서 또 2번째로 작은..

import java.io.*;import java.util.*;public class 마라톤1_10655 {    public static void main(String[] args) throws Exception {        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));                // 체크포인트 입력받기        int N = Integer.parseInt(br.readLine());        int cp[][] = new int[N][2];        for(int i = 0; i N; i++) {            StringTokenizer st = new StringToken..

import java.io.*;public class 달팽이_1913 {    public static void main(String[] args) throws Exception {                StringBuilder sb = new StringBuilder();                // 입력받기        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));        int N = Integer.parseInt(br.readLine());        int target = Integer.parseInt(br.readLine());        // 2차원 배열 생성        int board..

# 1일차의 최댓값, 2일차의 최댓값, 3일차의 최댓값.. 순으로 N일차의 최댓값까지 구한다import sysinput = sys.stdin.readline#  상담 가능 일수N = int(input())# 시간과 수익을 따로 입력받는다time, point = [0 for _ in range(N + 1)], [0 for _ in range(N + 1)]for i in range(1, N + 1):    time[i], point[i] = map(int, input().split())# dp 테이블 만들고, 1일부터 로직 시작dp = [0 for _ in range(N + 1)]for i in range(1, N + 1):    # 기존에 있던 값과 전날 값을 비교해 큰 값으..

import sys N, K = map(int, input().split()) # 물건 수, 버틸 수 있는 무게 item = [[]] # 물건 입력받기 (무게, 가치) for _ in range(N): item.append(list(map(int, input().split()))) dp = [[0 for _ in range(N + 1)] for _ in range(K + 1)] # dp테이블 만들기, 0행과 0열은 0으로 채우기 for x in range(1, K + 1): for y in range(1, N + 1): if x - item[y][0] >= 0: # 현재무게 - 현재물건무게 값이 0이상이라면 (dp테이블에 있다면, 담을 수 있다면) dp[x][y] = max(dp[x][y-1], dp[x..

a = [[]] # dp테이블과 인덱스를 동기화하기 위해 빈 리스트를 추가한다. b = [[]] for i in list(input()): a.append(i) for i in list(input()): b.append(i) # 0행과 0열 값을 모두 0으로 맞춰준다. # 첫번째 비교부터 공식을 적용하려면 이전 값이 존재해야 하기 때문에 맞춰주는 것. dp = [[0 for _ in range(len(a))] for _ in range(len(b))] for x in range(1, len(b)): for y in range(1, len(a)): if b[x] == a[y] : # 문자열이 일치할 경우 dp[x][y] = dp[x-1][y-1] + 1 # 좌측위 방향 값에서 +1 더한 값 else: # ..

# 끝나는시간으로 정렬하지 않으면 일찍 시작하고 아주 늦게 끝나는 회의에 말릴 수 있다 # 시작시간으로 정렬해야 회의목록을 순차적으로 돌면서 진행 가능하다 import sys input = sys.stdin.readline N = int(input()) # 회의 개수 talkList = [] # 회의 리스트 (시작시간, 종료시간) for _ in range(N): talkList.append(list(map(int, input().split()))) talkList.sort(key = lambda x: (x[1], x[0])) # 회의 리스트 정렬 ( 끝나는시간으로 정렬 후 시작시간으로 정렬 ) cnt = 1 # 회의개수 셀 변수 end = talkList[0][1] # 첫 회의 끝나는시간을 미리 초기화..

import sys input = sys.stdin.readline T = int(input()) # 테스트 케이스 개수 for _ in range(T): # 테스트 케이스 개수만큼 진행한다 N = int(input()) # 동전 종류 개수 coinBox = list(map(int, input().split())) # 동전 입력받기 coinBox.insert(0, 0) # 0번 인덱스에 0넣기. 첫번째 동전부터 점화식을 적용하기 위함. money = int(input()) dp = [[0] * (money + 1) for i in range(N + 1)] # 목표금액만큼 한 행을 길게, 동전갯수만큼 한 열을 길게 for i in range(N + 1): dp[i][0] = 1 # 동전이 뭐든 간에 0을 ..

x = int(input()) d = [0] * (x + 2) d[1] = 1 d[2] = 2 for i in range(3, x + 1): d[i] = (d[i-1] + d[i-2]) % 15746 print(d[x]) 다이나믹 프로그래밍 문제이다. 점화식만 찾으면 아주 간단하게 해결할 수 있다. 계산값을 저장해둘 DP테이블(리스트 d)를 생성하고, 초기값을 넣어준다. d[1]엔 1길이의 수열에서 나올 수 있는 경우의 수의 개수, d[2]엔 2길이, d[x]엔 x길이의 수열에서 나올 수 있는 경우의 수의 개수가 들어간다. 타일 경우의 수를 구하는 것은 언뜻 답이 없어 보이지만, 규칙이 있다. 현재 값들에 1을 붙이고, 이전 값들에 00을 붙이면 그게 다음 값이 된다. 즉 N=4 일 때의 경우의 수를 구..

string = input().split('-') result = 0 for i in string[0].split('+'): result += int(i) for i in string[1:]: for j in i.split('+'): result -= int(j) print(result) 그리디 알고리즘 문제이다. 문제 원리는 매우 간단하다. 숫자, '+', '-' 세 가지로만 구성된 문자열이 주어진다. 숫자로 시작해서 숫자로 끝나고, 연산자는 숫자 사이사이에 온다. 여기서 괄호를 원하는 곳에 추가해, 가장 작은 값을 만들어내면 된다. 근데 조금 생각해보면 알 수 있겠지만, 첫번째로 등장하는 '-' 이후의 값들은 전부 뺄 수 있다. 그리고 '-' 이전의 값들은 전부 더하면 된다. 문제의 원리는 쉽다. 하..