본문 바로가기

Probelm Solving/BOJ19

BOJ10714 케이크 자르기 2 10714번 케이크 자르기 2 자를 수 있는 케이크 조각의 크기가 주어질 때, JOI는 최선을 다해 케이크를 자르고, IOI는 양 끝 조각 중 무조건 큰 조각을 자른다. JOI가 얻을 수 있는 조각 합의 최댓값을 구해야 한다. 최선을 다하는 문제와 비슷하다. 다른 점은 JOI만 최선을 다한다 ⇒ dp배열에 두 명이 가진 케이크 양을 저장할 필요 없이 JOI가 얻게 된 조각 합의 양만 저장하면 된다. 케이크 조각은 직선형 배열이 아닌 원형 배열이다. 즉 시작과 끝이 정해져있지 않다 ⇒ i, j의 대소에 관계없이 전체 dp 배열을 채워야 한다. 가령 N=5일 때 dp[ 2 ][ 4 ]는 2, 3, 4번째 조각이 남아있을 때 dp[ 4 ][ 2 ]는 4, 5, 1, 2번째 조각이 남아있을 때 JOI가 얻은 케.. 2021. 1. 30.
BOJ2342 Dance Dance Revolution 2342번 DDR 뭔가 경찰차랑 비슷한 느낌의 DP 눌러야하는 DDR의 발판 번호가 주어지면 발판을 순서대로 누르기 위한 최소의 힘을 구해야 한다. a[ i ][ j ]=이번 발판까지 고려하여 오른발이 i, 왼발이 j를 누를 때 사용한 최소의 힘 STEP 1. 발의 움직임에 따라 사용하는 힘을 배열에 저장 사차원 배열을 이용했다. p[ a ][ b ][ c ][ d ]=오른발 a, 왼발 b에서 오른발 c, 왼발 d 가 될 때 사용하는 힘 //same posit: 1i,j -> i,j i=0-4 j=0-4 //0->1/2/3/4: 2i,0 -> i,j i=0-4 j=1-4 //moving adj: 3i,j -> i,j+1 //moving opp: 4 //STEP 1. Set Power p int p[5][.. 2021. 1. 30.
BOJ2618 경찰차 BOJ2618 경찰차 dp[ i ][ j ] dist = 마지막으로 A, B가 각각 i, j를 처리했을 때 움직인 총 거리 T = 가장 최근 사건을 처리하기 직전의 상태 STEP 1. w=1일 때 dp[ 1 ][ 0 ], dp[ 0 ][ 1 ] 갱신한다. STEP 2. w=2~W일 때 dp[ * ][ w ]와 dp[ w ][ * ]를 구한다. w-1번째, w번째 사건을 처리하는 경찰차가 각각 무엇인지에 따라 구해주면 된다. A-A: [ w-1 ][ * ] → [ w ][ * ] A-B: [ w-1 ][ * ] → [ w-1 ][ w ] B-A: [ * ][ w-1 ] → [ w ][ w-1 ] B-B: [ * ][ w-1 ] → [ * ][ w ] ㆍ*에 들어갈 수는 0부터 w-2까지여야 한다. ㆍdis.. 2021. 1. 29.
BOJ13976 타일 채우기 2 BOJ13976 타일 채우기 2 BOJ2133 타일 채우기 같은 문제다. 다만 N의 범위가 다르다. 2133번은 1≤N≤30이기 떄문에 수열의 값을 모두 구해도 된다. 13976번은 1≤N≤1,000,000,000,000,000,000=10^18이기 때문에 행렬의 거듭제곱을 이용하여 풀어야 한다. 필기만 옮기려고 했으나 코드까지 첨부 더보기 #include #include using namespace std; long long DIV = 1000000007; struct Matrix { long long a[2][2]; Matrix() { a[0][0] = a[0][1] = a[1][0] = a[1][1] = 0; } Matrix(long long x, long long y, long long z, lo.. 2021. 1. 28.
BOJ11062 카드 게임 BOJ11062 카드게임 두 명 모두 최선의 전략으로 임할 때 얻는 점수를 구해야 한다. 게임이론 문제 분명 이전에도 본 적 있는 문제인데 헷갈려서 제꼈던 문제였을 것,, 최선의 전략으로 임한다는 말을 이해하기가 어려웠다. 이해하기보단 적용하기가? 미래 예측을 기똥차게 하겠단 소린데 어디까지 생각해야 할지, 완전 끝까지 생각하려면 어떻게 구현해야 할지가 막막했다. pair를 이용한 2차원 array로 풀었다. 재귀를 이용했으면 더 편했을 것도 같은데,, 구현할 때는 구할 수 있는 값부터 전체 배열을 채우는 식으로 빌드업함 dp[ i ][ j ] = 카드 j ~ i 로 게임을 진행할 때 { 먼저 시작한 사람의 점수, 상대방의 점수 } 카드 j ~ i 로 게임을 진행, X와 Y중 X가 먼저 카드를 뽑는다면 .. 2021. 1. 28.
BOJ1019 책 페이지 www.acmicpc.net/problem/1019 1019번: 책 페이지 첫째 줄에 0이 총 몇 번 나오는지, 1이 총 몇 번 나오는지, ..., 9가 총 몇 번 나오는지를 공백으로 구분해 출력한다. www.acmicpc.net 이런 거 초등학생 때 많이 풀었던 것 같은데,, 경우의 수같은 거 배울 때 나오는 문제임 처음엔 2459가 있을 때 0001~2000 2001~2400 2401~2450 2451~2459 이렇게였나 뭐 비슷하게 수의 범위로 나눠서 생각하는 걸 시도했음. (실패함) 자릿수로 나눠서 생각하는 게 더 편했다. 1이 등장하는 횟수는 일의 자리가 1인 수의 개수 + 십의 자리가 1인 수의 개수 + ... 이거니까 N=2458, (1) 일의 자리가 k인 수의 개수 = _ _ _ k 인 수.. 2021. 1. 12.
BOJ13977 이항 계수와 쿼리 www.acmicpc.net/problem/13977 13977번: 이항 계수와 쿼리 \(M\)개의 자연수 \(N\)과 정수 \(K\)가 주어졌을 때 이항 계수 \(\binom{N}{K}\)를 1,000,000,007로 나눈 나머지를 구하는 프로그램을 작성하시오. www.acmicpc.net = 16134 조합(Combination) 15791 세진이의 미팅 페르마의 소정리에 의해 p가 소수이고 a가 정수일 때, a^p≡a (mod p) ⇒ a^(p-1)≡1 (mod p) ⇒ a^(p-2)*a≡1 (mod p) 즉 mod p에서 a의 역원이 a^(p-2)가 된다. a^p구하는 건 재귀함수로 해주고 long long 주의 13977번의 경우 N!, K!, (N-K)!을 모두 구해야하니까 while 돌리기 .. 2021. 1. 12.
BOJ11003 최솟값 찾기 www.acmicpc.net/problem/11003 11003번: 최솟값 찾기 N개의 수 A1, A2, ..., AN과 L이 주어진다. Di = Ai-L+1 ~ Ai 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오. 이때, i ≤ 0 인 Ai는 무시하고 D를 구해야 한다. www.acmicpc.net i-L+1 ~ i 번 째 수 중 최솟값 출력 덱 이용하기 내 앞의 수가 나보다 크다 ⇒ 그 수는 필요없다. 내 앞의 수가 나보다 작다 ⇒ 내가 나중에 필요할 수도 있다. push는 뒤에서만 해준다. 덱을 앞에서부터 볼 때 읽은 순으로, 값은 오름차순으로 정렬되도록 한다. 1. 범위를 벗어난 값은 pop front 2. 앞의 수 중 나보다 큰 것 pop back * 이때 앞의 수의.. 2021. 1. 12.
BOJ2478 자물쇠 www.acmicpc.net/problem/2478 2478번: 자물쇠 처음 k-왼쪽밀기의 k를 첫째 줄에, (p,q)-구간뒤집기의 p와 q를 빈칸을 사이에 두고 둘째 줄에, 그리고 마지막 k-왼쪽밀기의 k를 셋째 줄에 출력한다. 만일 답이 여럿일 경우에는 그 중 하나만 출력 www.acmicpc.net 입력에 맞는 답 (k1, p, q, k2)가 여러 개 존재한다. 아래처럼 둘 중 뭐가 돼도 상관없다는 걸 먼저 파악함. 그 다음엔 가장 구하기 편한 걸 구하기로 했다. (3, 5, 7, 3): 12345678 → 45678123 → 45672183 → 72183456 (5, 3, 5, 1): 12345678 → 67812345 → 67218345 → 72183456 아래 여섯 가지 예시로 생각해보았다. .. 2021. 1. 7.

티스토리툴바