https://www.acmicpc.net/problem/22940 22940번: 선형 연립 방정식 하나 이상의 미지수에 대해 최고차항의 차수가 1을 넘지 않는 방정식을 선형 방정식이라 한다. 족, 다음과 같은 식을 의미한다. A1x1 + A2x2 + ... + Anxn = B 선형 연립 방정식이란 유한개의 선형 방 www.acmicpc.net 다른 풀이가 당연히 있겠지만, 컴퓨터공학을 전공한다면 Gauss - Jordan 소거법을 사용할 듯 하다. 선형대수학에서 배운 기본 행 연산을 통해 계수행렬을 RREF(Reduced Row Echelon Form)으로 만들는 과정을 그대로 구현하면 된다. 이 문제에서는 주어지는 행렬이 최대 6 by 6이고, 계수들도 모두 10까지의 자연수로만 이루어져 있는데 과정..

https://www.acmicpc.net/problem/27650 27650번: 마법박스 다음을 표준 출력 스트림(stdout)으로 한 줄에 출력하여, $i$ 이하의 $2$ 이상의 양의 정수가 마법박스에 모두 들어있는지 질의할 수 있다. 질의에 대한 답변은 모두 들어있다면 $1$, 그렇지 않다면 $0 www.acmicpc.net 인터렉티브 문제로 채점 방식이 특이하다. "?"를 출력하여 문제에게 질문해야하고, 문제가 답을 주면 범위를 줄여서 물어보고... 그러다가 "!"로 답을 출력해야한다. 이 문제에서는 질문할 수 있는 횟수가 20번이므로 스무고개라고 생각하면 된다. 처음으로 이런 유형을 풀어봤고 문제랑 대화하는 느낌이 들어서 재밌었다. 마법박스에 들어있는 수 중에서 가장 작은 정수를 찾으면 되는데,..

https://www.acmicpc.net/problem/20500 20500번: Ezreal 여눈부터 가네 ㅈㅈ 문제의 답을 $1\,000\,000\,007$로 나눈 나머지를 출력한다. www.acmicpc.net 우선 1과 5로만 이루어진 숫자가 15의 배수가 되기 위해서는 마지막 숫자가 5로 끝나야 한다. 마지막 숫자가 5로 끝나면 경우의 수는 3가지이다. 15로 나눴을 때 나머지가 5인경우, 10인 경우, 0인 경우. dp[i][0] 을 i자리수면서 나머지가 0인 경우, dp[i][1]을 i자리수면서 나머지가 5인경우, dp[i][2]를 i자리수면서 나머지가 10인 경우로 생각했다. 저렇게 나누고 4자리수까지 나머지가 0,5,10인 경우를 세 보았는데 다음과 같은 규칙이 보였다. dp[i][0] ..

https://www.acmicpc.net/problem/10835 10835번: 카드게임 첫 줄에는 한 더미의 카드의 개수를 나타내는 자연수 N(1 ≤ N ≤ 2,000)이 주어진다. 다음 줄에는 왼쪽 더미의 카드에 적힌 정수 A(1 ≤ A ≤ 2,000)가 카드 순서대로 N개 주어진다. 그 다음 줄에는 오 www.acmicpc.net 1. 왼쪽 카드만 버리는 경우 2. 왼쪽 카드와 오른쪽 카드를 버리는 경우 3. "왼쪽 카드 < 오른쪽 카드" 를 만족하여 오른쪽 카드만 버리는 경우 이 세가지 경우를 모두 고려해주어야 한다. dp[left][right] 는 왼쪽 카드와 오른쪽 카드를 left장, right장 버렸을 때 점수의 최댓값이다. 코드는 다음과 같다. #include #include using ..

https://www.acmicpc.net/problem/14728 14728번: 벼락치기 ChAOS(Chung-ang Algorithm Organization and Study) 회장이 되어 일이 많아진 준석이는 시험기간에도 일 때문에 공부를 하지 못하다가 시험 전 날이 되어버리고 말았다. 다행히도 친절하신 교수님께서 아래와 www.acmicpc.net 배낭 문제랑 똑같은 문제이다. 배낭문제는 2차원 Dp를 이용해서 Buttom-up으로 풀었었는데 배낭문제는 1차원 Dp를 이용하면서 Top-down으로 풀어주는게 더 효율적이다. 배낭문제를 풀어본 사람이라면 알다시피 2차원 배열에서 굳이 값을 채우지 않아도 되는 배열까지 값을 채우기 때문에 메모리와 시간이 Top-down에 비해 오래걸린다. 주어진 시간..

https://www.acmicpc.net/problem/9764 9764번: 서로 다른 자연수의 합 첫째 줄에, 테스트 케이스의 개수 T (1 ≤ T ≤ 20)이 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, N이 주어진다. www.acmicpc.net 중복된 자연수를 사용할 수 없기 때문에 우리가 흔히 아는 동전 문제와 비슷하게 생각할 수 있지만 살짝 다르다. 동전 문제는 button up으로 간단하게 해결 할 수 있다. 하지만 이 문제는 buttom up 보다는 top down이 더 효율적이고 풀이도 간단한 문제이다. 두 풀이를 모두 올리니 공부할 때 참고 하면 되겠다. 먼저 Dp 이므로 큰 문제(우리의 목표)를 작은 문제로 나눠야 한다. 동전 문제에서는 2000원이 되는 경우를 1원이 되..