컴공과고씨

https://www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 문제 간단 정리 n * 3 개의 행렬 칸이 있고 각 칸에는 숫자가 적혀 있음. 맨 위 부터 출발 하여 내려오는데 바로 아래와 한 칸 대각선으로만 이동 가능함. 이 때 얻을 수 있는 최대, 최소 점수를 구하시오. 문제 해결 방법 이 문제 같은 경우 위에서 내려온다는 생각을 하지말고 도착할 칸이 위에서 내려오는 점수를 받는 다고 생각하면 쉽다. 이런식으로 첫번째 칸은 점수를 바로 위와 그 옆에서 밖에 올 수 없기 ..

https://www.acmicpc.net/problem/2407 2407번: 조합 n과 m이 주어진다. (5 ≤ n ≤ 100, 5 ≤ m ≤ 100, m ≤ n) www.acmicpc.net 문제 간단 정리 이 문제는 말 그대로 nCm을 구해주면 되는 문제이다. nCm 이란 서로 다른 n개 중 m개를 뽑는 방법을 말한다. 구하는 법은 n!/m!(n-m)! 이다. 문제 해결 방법 이런 문제 같은 경우 공식을 구현하기 할 수는 있겠지만 답이 겁나게 크게 나오는 걸 볼 수 있다. 즉, c++에서는 저런 큰 수를 정수로 담을 변수가 없기도 하고 공식 구현 하더라도 일일이 다 곱하는 팩토리얼이 있기 때문에 시간초과가 걸릴 수 밖에 없다. 일단 써봐서 규칙을 찾아보는 것이다. 1C0 1C1 2C0 2C1 2C2..

https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 문제 정리 집을 3가지 색으로 칠할 수 있음. 각 집마다 각 색으로 칠하는 비용이 다름. 각 집의 색깔은 바로 앞 집과 바로 다음 집의 색깔과 같으면 안됨. 비용을 최소로 칠하는 비용은? 문제 해결 방법 이 문제의 경우 다이나믹 프로그래밍을 이용하면 쉽게 풀 수 있다. 일단 dp[3][n]이라는 배열을 만든다. 이 배열의 의미를 먼저 알아보자. 앞에 3이라는 것은 3가지 색깔..

https://www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 문제 정리 1. 행렬이 주어짐. 2. 시작 좌표 (x1,y1)이 주어지고 도착 좌표 (x2,y2)가 주어짐 3. 좌표 사이에 있는 값의 합들을 구해야함. 예를 들어 초록색이 시작 좌표, 파란색이 끝 좌표라고 하면 저런식으로 보라색 빗금의 부분의 합들을 구해주면됨. 문제 해결 방법 그 전 구간 합 구하기를 해보면 알듯이 일일이 for문을 돌리면서 구해주면 ..

https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 문제를 보고 규칙이 있을 것 같아서 쭉 써보았다. 1 -> 1개 2 -> 2개 3 -> 4개 4 -> 7개 5 -> 13개 여기서 점화식을 알아낼 수 있는데 n = (n-1) + (n-2) + (n-3)번째 라는 점화식을 볼 수 있었다. 점화식은 다이나믹 프로그래밍으로 풀면 쉽게 풀 수 있어 다이나믹 프로그래밍을 이용하여서 문제를 풀었다. 단계별 문제 풀이 1. dp 배열 선언 2. 초기값 dp[1], dp[2], dp[3] 값 입력 3. 점화식을 이용해서 풀어줌 전체코드 1 2 3 4 5 6 ..