겜돌이의 개발일지

문제 백준 9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 풀이 점화식을 이용합니다. i 번째에서 더해줄 수 있는 방법의 가지수는 3가지입니다. 1더하기, 2더하기, 3더하기 i 번째 오는 방법을 i+1, i+2, i+3에 각각 더해줍니다. 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 #include using namespace std; int dp[14]; int main() { int t; cin >> t; dp[0] = 1; for (int i = 0; i n; cout

문제 https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 풀이 유명한 0-1 배낭 문제입니다. dp[i][j]의 의미는 i개까지의 물건을 넣는 경우에서 무게가 j일때 가치의 최대값입니다. 예제 입력으로 분석해보겠습니다. n / k 1 2 3 4 5 6 7 0 0 0 0 0 0 0 0 1 0 0 0 0 0 13 13 2 0 0 0 8 8 13 13 3 0 0 6 8 8 13 14 4 ..

문제 백준 15681 15681번: 트리와 쿼리 트리의 정점의 수 N과 루트의 번호 R, 쿼리의 수 Q가 주어진다. (2 ≤ N ≤ 105, 1 ≤ R ≤ N, 1 ≤ Q ≤ 105) 이어 N-1줄에 걸쳐, U V의 형태로 트리에 속한 간선의 정보가 주어진다. (1 ≤ U, V ≤ N, U ≠ V) www.acmicpc.net 풀이 리프 노드는 자식이 없으므로 서브 트리의 정점 개수는 자기 자신 1개입니다. 따라서 dp 배열을 1로 초기화해줍니다. 루트 노드부터 dfs를 실행하고, 서브 트리의 탐색이 모두 끝났다면 부모에게 자신의 서브 트리 값을 더해줍니다. 부모가 -1인 경우는 루트 노드이므로 더하지 않습니다. 예제를 보겠습니다. 숫자는 해당 정점에서의 서브 트리의 정점 개수이고, 괄호 안은 방문 순서..

문제 백준 17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 풀이 bfs와 dp를 섞은 듯한 재밌는 문제였습니다. q는 순서대로 현재 파이프 끝의 x좌표 / y좌표 / 상태를 저장합니다. q에다가 push와 pop을 반복하면서, 갈 수 있는 경로의 수를 파악합니다. 각각의 상태에 대해 취할 수 있는 다음 상태를 하드 코딩 했는데, 따로 함수를 만들었다면 더욱 깔끔한 코드가 되었을 것 같습니다. 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17..

문제 백준 11057 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수 www.acmicpc.net 풀이 n = 3일때 까지의 예시입니다. 첫번째 열은 1로 초기화를 해줍니다. 두번째 열은 길이가 1인 오르막 수 입니다. 1~9까지 10개가 있습니다. 세번째 열은 길이가 2인 오르막 수 입니다. 예를 들어서, 9x에 들어갈 수 있는 x는 9 1개 입니다. (누적 : 1개) 8x에 들어갈 수 있는 x는 8, 9 2개 입니다. (누적 : 3개) 7x에 들어갈 수 있는 x는 7, 8, 9 3개 입니다. (누적 ..

문제 백준 5557 5557번: 1학년 상근이가 1학년 때, 덧셈, 뺄셈을 매우 좋아했다. 상근이는 숫자가 줄 지어있는 것을 보기만 하면, 마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 사이에는 '+' 또는 '-'를 넣어 등식을 만들며 놀 www.acmicpc.net 풀이 점화식이 은근 간단한데 구현에 시간이 오래걸렸습니다. dp[i][j]는 i+1번째 차례에 +, - 연산으로 숫자 j를 만들 수 있는 경우의 수를 뜻합니다. dp[0][num[0]] 부터 시작하므로 1을 넣어줍니다. 그 후 루프를 돌면서 dp[i-1][j]값이 0보다 클 경우(가는 방법이 존재할 경우) 더한 값과 뺀 값을 비교하여 조건(0이상 20이하)을 만족한다면 dp에 저장합니다. 루프가 끝난 뒤 num[N-1] 값이 나오는 경..