유형: dp 문제: https://www.acmicpc.net/problem/15489 15489번: 파스칼 삼각형 첫째 줄에 양의 정수 R, C, W가 공백을 한 칸씩 두고 차례로 주어진다. (단, 2 ≤ R+W ≤ 30, 2 ≤ C+W ≤ 30, 1 ≤ W ≤ 29, C ≤ R) www.acmicpc.net 풀이 길이가 30까지인 파스칼의 삼각형을 미리 계산해둔 후, 입력값의 크기만큼 해당 값을 더해주면 된다. 입력값에서 r, c는 인덱스 크기에 맞춰 -=1을 해줘야 한다. (인덱스는 0부터 시작하기에) 세로의 크기는 r-1이상 r+w미만, 가로의 크기는 c-1이상 c+width미만이다. width의 크기는 첫번째 for문에서 한번씩 +=1을 해주면 된다. #include "vector" #inclu..
유형: dp 문제 리스트: https://solved.ac/search?query=돌 게임 solved.ac - 검색 solved.ac 돌 게임 문제는 조금씩 변형해서 여러 문제가 있다. 1, 3개씩 가져가는 경우, 4개씩도 가져가는 경우, 마지막으로 가져간 사람의 승패를 반대로 하는 경우가 주로 있다. 문제 자체도 다소 추상적이라 감을 잡기 쉽지 않지만, 이런 문제는 규칙만 알면 O(1)로도 풀 수 있다. 몇달 전에 풀긴 했지만, 나는 1, 3개씩 가져가는 경우에서 규칙을 찾았었다. 개수를 2로 만들면 1밖에 못가져가기에 무조건 2로 만든 사람이 이긴다. 이걸 활용했던 것 같다. 패턴을 파악하기 위해 1부터 시작해서 경우의 수를 그려나갔다. 6~7정도가 되면 패턴이 보인다. 1, 3, 4개씩 가져가는 ..
유형: dp 문제: https://www.acmicpc.net/problem/14916 14916번: 거스름돈 첫째 줄에 거스름돈 액수 n(1 ≤ n ≤ 100,000)이 주어진다. www.acmicpc.net 입출력 형식 계산할 값이 들어오면 solution 함수에서 계산한다. 풀이는 solution 함수만 올림. #include "iostream" #include "vector" using namespace std; int solution(int n){ // ... return 0; } int main(){ int total; cin >> total; cout
