소심야채

https://www.acmicpc.net/problem/2365 2365번: 숫자판 만들기 입력의 첫째 줄에는 행(열)의 크기 N이 주어진다(1 ≤ N ≤ 50). 둘째 줄에는 N개의 정수가 주어진다. 주어지는 정수는 1행부터 N행까지의 합을 차례대로 나타낸다. 셋째 줄에는 N개의 정수가 주어 www.acmicpc.net [문제설명] - N*N 숫자판(숫자판의 수들은 주어지지 않음)의 N개의 행과 N개의 열의 합이 주어진다. - 숫자판의 배정된 수들은 0이상의 정수이다. - 조건을 만족하는 배정된 수 중에서 최댓값을 최소로 하는 숫자판을 찾아야한다. [문제풀이] - 지문에서 주어지는 입력을 시각화하면 아래와 같습니다. c* = max(a, b, c, d)일때 c*의 값을 최소로하는 숫자판의 형태를 찾아..

https://www.acmicpc.net/problem/27469 27469번: 퀸 움직이기 숙제를 하지 않고 체스와 조합론에 빠져있던 은재가 생활관에 체스판을 하나 들고 왔다. 이 체스판은 특이해서 $8 \times 8$ 형태의 기본적인 판 뿐만 아니라 $17 \times 19$ 크기나 심지어 $1 \times 100$ www.acmicpc.net [문제설명] - N행 M열로 구성된 체스판의 정보와 퀸의 시작 좌표와 도착 좌표가 주어진다. - 체스판 각 칸에는 장애물(#)이 있거나 빈 칸(.)으로 구성되어 있다. - 퀸은 8방향(상하좌우, 대각선)으로 장애물이 없을경우 거리 제한없이 이동가능하다. - 두 번 연속으로 같은 방향으로 움직일 수 없다. - 시작 좌표로 부터 K번 이동하였을 때 도착 좌표로..

https://www.acmicpc.net/problem/2961 2961번: 도영이가 만든 맛있는 음식 첫째 줄에 재료의 개수 N(1 ≤ N ≤ 10)이 주어진다. 다음 N개 줄에는 그 재료의 신맛과 쓴맛이 공백으로 구분되어 주어진다. 모든 재료를 사용해서 요리를 만들었을 때, 그 요리의 신맛과 쓴맛은 www.acmicpc.net [문제설명] - n개의 재료를 각각 사용 또는 사용안해도 된다. - 각 재료는 신맛 S와 쓴맛 B를 가지고 있다. - 재료 선택을 마친 후 선택된 재료의 신맛을 곱하고 쓴맛은 더했을 때 두 값의 가장 작은 차이를 출력해야 한다. - 재료는 적어도 하나 사용해야 한다. [문제풀이] - n개의 재료를 사용하거나 사용안해도 무방하니 재료선택의 총 경우의 수는 2^n입니다. - n이..

https://www.acmicpc.net/problem/26518 26518번: 수열의 극한값 첫 번째 줄에 정수 $b$, $c$, $a_1$, $a_2$가 공백으로 구분되어 주어진다. $(1 \leq b, c, a_1, a_2 \leq 10^9)$ www.acmicpc.net 문제풀이 $$a_i = b*a_{i-1} + c*a_{i-2} (i \geq 3)$$ 수열 a가 주어졌을때 $$\lim_{n \to inf}\frac{a_n}{a_{n-1}}$$ 값을 구하는 문제로써 문제에서 항상 이 값이 수렴되어짐이 보장되어 있다. 문제에서 주어지는 정수범위로 인해 순차적으로 수열값(a_n)을 구하면서 극한 값을 접근하는 시도는 long long int를 사용하더라도 오버플로우가 발생한다. 따라서 적절하게 식..

www.acmicpc.net/problem/17142 17142번: 연구소 3 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고 www.acmicpc.net 더보기 문제를 해결하기 위해선 크게 2가지 함수가 필요할 것 같다. 1. 입력에 주어진 바이러스(x) 중에서 M개의 바이러스를 선택해야 한다. --> pick 2. 1번에서 선택한 바이러스를 퍼트렸을 때 결과 값 반환 --> bfs 2번을 시도하였을 때 두 가지 결과가 발생한다. 2-1. 모든 빈칸에 바이러스를 퍼트림 2-2. 모든 빈칸에 바이러스를 퍼트리지 못함 2-2번을 판단하기 쉬운 방법은 N^2의 초기상태를 입력..

www.acmicpc.net/problem/6064 6064번: 카잉 달력 입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터는 한 줄로 구성된다. www.acmicpc.net [잡담] 더보기 정수론 공부의 필요성을 느껴 유투브 보면서 기초부터 공부하고있다. 모듈러 기초연산부터 페르마 소정리, 중국인의 나머지 정리, 뤼카의 정리등 처음볼때는 전혀 이해가 안갔지만 이항계수 정리등 블로그로 부족한 개념을 채우다 보니 어느정도 이해하게 되었다. 지금이라도 수학공부를 꾸준히 해놔야겠다. [코드] 더보기 #include using namespace std; typedef long long LL; ..

www.acmicpc.net/problem/2336 2336번: 굉장한 학생 첫째 줄에 N(1 ≤ N ≤ 500,000)이 주어진다. 다음 세 개의 줄에는 각 시험에서 1등인 학생부터 N등인 학생이 순서대로 주어진다. 학생의 번호는 1부터 N까지 매겨져 있다. www.acmicpc.net 이 문제는 스위핑 + 세그먼트 트리를 이용한 문제이다. 체인점(2472) 문제와 풀이가 유사하다. "굉장한 학생 수"를 구하기위해 "전체 학생수" - "굉장하지 않은 학생수"를 빼면 되고, "굉장하지 않은 학생수"를 구하기 위해 a.x < b.x && a.y < b.y && a.z < b.z **(x,y,z)는 시험등수, (a,b)는 학생 를 만족하는 b학생은 굉장하지 않은 학생이된다. (a학생이 b학생보다 대단하기 때..

www.acmicpc.net/problem/11333 11333번: 4×n 타일링 각 테스트 케이스마다 문제의 정답을 1,000,000,007로 나눈 나머지를 출력한다. www.acmicpc.net 기존의 2 x n 타일링 문제에서 파생된 문제여서 점화식 도출이 쉬울거라 예상하였지만 결론적으로 매우 복잡하였고 스택오버플로우에서 나올수있는 경우의수를 도움받아 식을 찾게되었고 바텀업으로 n의 최대범위까지 답을 채운후 TC만큼의 질의를 바로 응답하였다. 각 a, b, c, d, f 값을 0, 1, 2, 3, 4 로 치환하여 dp배열을 채웠다. 더보기 #include using namespace std; const int MAX_N = 1e4+4; const int MOD = 1e9+7; int dp[MAX_N..