Probelm Solving42 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. 구현 (1) 18809번 Gaaaaaaaaaarden BFS BF 그래프 구현 시뮬레이션 14865번 곡선 자르기 구현 3954번 Brainf**k 인터프리터 자료구조 구현 스택 3678번 카탄의 개척자 구현 시뮬레이션 17472번 다리 만들기 2 BFS BF 그래프 구현 MST 16637번 괄호 추가하기 BF 17135번 캐슬 디펜스 BFS BF 그래프 구현 시뮬레이션 17406번 배열 돌리기 4 BF 구현 진짜 나는 좌표가 너무 헷갈린다. 공간지각능력이 좋은 사람은 아니라... 시각화가 너무나 중요하다. 과연 이 필기를 다시 꺼내볼 일이 있을 것인지,, 2021. 1. 29. 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. 기하학 (1) 고등수학 재밌다. 더보기고민을 안하고 풀어도 됨 바깥 삼각형의 중심 벡터 열심히 계산해서 연립방정식 풀면 된다 너무 재밌따. 피자 배치 닮음비 계산하고 지수 늘려주면서 K번째 피자를 찾는다. 외계인의 침투 모의고사 18번 문제 느낌임 아니면 26번,, 대충 먼말인지 알지 Cows 다각형은 삼각형으로 나눌 수 있다. 삼각형의 넓이는 K-고등수학을 배웠다면 구할 수 있다. 여기선 다만 점을 정렬해줘야 하는데 이때 컨벡스헐 개념이 필요했던 것 같네컨벡스헐 솔직히 아직 완벽히 알지 못하는 상태라 다음에 정리해줘야겠다. 2021. 1. 19. 행렬의 제곱 분할 정복, DP 문제에서 N이 아주 크게 주어지는 경우 자주 이용됨 분할 정복을 이용한 거듭제곱에 있는 문제 거의 다 이런 문제일 것 같다. struct로 행렬을 구현해 곱셈 연산자 오버로딩. 15행에 출력 조건과 수의 범위에 따라 MOD연산 등을 추가한다. 당연하지만 이때 음수 MOD연산도 주의하자,, 통수 맞을 수 있음,, struct Matrix { int size; vector a; Matrix() { size = 0; } Matrix(int n) { size = n; a = vector(n, vector(n)); } Matrix operator *(const Matrix& X) { Matrix RES(size); for (int i = 0; i < size; i++) { for (int j =.. 2021. 1. 16. 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. 이전 1 2 3 4 5 다음
