https://www.acmicpc.net/problem/2225 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net dp Table을 그리면 쉽게 점화식을 구할 수 있는 문제였다. dp Table의 각 칸은 모든 경우의 수를 직접 써내려가며 구해도 되지만, 순열공식을 통해 더 빠르게 구할 수 있다. 예를 들어, n=5, k=3 일 때 각 조합의 경우의 순열의 개수는, (3,0,0) -> 3!/2! = 3 (2,1,0) -> 3! = 6 (1,1,1) -> 3!/3! = 1 따라서, 3+6+1 = 10 위와 같이 n=8, k=4 까지 구한 dp Table은, k\n 1 2 3 4 5 6 7 8 1 1 1 1 1 1 1 1 1 2 2 3 4..
백준
https://www.acmicpc.net/problem/2011 >s; int size = s.size(); if(s[0]=='0'){ cout
https://www.acmicpc.net/problem/17267 17267번: 상남자 CTP의 대표 상남자 영조는 자유롭게 이동하는 것을 좋아한다. 그렇지만 영조는 상남자이기 때문에 위아래로만 간다. 따라서 위, 아래로는 얼마든지 이동할 수 있지만 왼쪽, 오른쪽으로는 이동하지 않는다. 하지만 영조의 행동이 답답한 영조의 친구 보성이는 영조가 위, 아래로만 가는 걸 막기 위해 영조와 같이 다니며 왼쪽으로 최대 L번 오른쪽으로 최대 R번만큼 이동할 수 있게 영조를 도와준다. 영조와 보성이는 지도 밖으로는 나가지 않는다. 갈수 있는 땅, 벽의 www.acmicpc.net 처음 봤을 때, BFS문제인 것은 쉽게 유추할 수 있었지만, 쉽게 틀릴 수 있는 문제였다. 일반적인 BFS처럼 상하좌우 한칸씩 탐색해가며..
https://www.acmicpc.net/problem/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼이 주어지며, 같은 버튼이 여러 번 주어지는 경우는 없다. www.acmicpc.net 깊게 생각해서 오히려 더 헤맸던 문제였다. 브루트포스로 접근하니 금방 풀린 문제이다. 처음 시작하는 채널은 100번. 리모컨의 부서진 버튼은 배열에 따로 체크해둔다. 그리고, 이 문제에서 가능한 모든 채널을 0번부터 탐색해준다. 약 100만 채널까지 탐색하면 되겠다. 그 채널을 가기 위해 필요한 버튼을 누르는 횟수(0번은 불..
https://www.acmicpc.net/problem/17219 17219번: 비밀번호 찾기 첫째 줄에 저장된 사이트 주소의 수 N(1 ≤ N ≤ 100,000)과 비밀번호를 찾으려는 사이트 주소의 수 M(1 ≤ M ≤ 100,000)이 주어진다. 두번째 줄부터 N개의 줄에 걸쳐 각 줄에 사이트 주소와 비밀번호가 공백으로 구분되어 주어진다. 사이트 주소는 알파벳 소문자, 알파벳 대문자, 대시('-'), 마침표('.')로 이루어져 있고, 중복되지 않는다. 비밀번호는 알파벳 대문자로만 이루어져 있다. 모두 길이는 최대 20자이다. N+2번째 줄부터 www.acmicpc.net 사이트 주소와 비밀번호를 페어로 묶은 벡터를 정렬하여, 이분탐색으로 사이트 주소의 위치번호를 찾아내면 쉽게 풀 수 있는 문제이다...
