컴공과고씨

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/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 문제 정리 7 3 8 8 1 0 2 7 4 4 처럼 삼각형이 주어짐 이때 삼각형의 크기가 주어지는데 높이를 나타냄 이 삼각형의 크기는 4임. 이렇게 해서 위에서 부터 숫자를 더해 밑으로 내려온다. 내려갈때는 왼쪽, 오른쪽 대각선으로 이동이 가능하다. 이때 숫자의 최대 합은? 문제 해결 방법 일단 다이나믹 프로그래밍을 이용해서 문제를 풀어야한다. 그리고 쉽게 문제를 풀기 위해 위 삼각형을 0 7 ------ 1번 줄 0 3 8 ------ 2번 줄 0 8 1 0 ----..

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/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 이 문제같은 경우 다이나믹 프로그래밍에 대표적인 문제라고 할 수 있다. 각 경우에 대해서 최선의 선택을 하면서 가면 되는데 이 말을 이해하기 위해서는 직접해보는 것이 좋다. 표를 직접 그려봤다면 이게 무슨 원리인지 알 것이다. 자신이 채우고 있는 행의 최선의 선택은 1. dp[i][j] = dp[i][j-현재 물건 무게] + 현재 ..

https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 이런 문제의 경우 각 경우 마다 최적의 경우의 수를 선택하면서 가면 된다. 저런식으로 각 자리를 늘려가면서 A에서 C가 들어갔을 때 LCS의 경우 0 AC와 C의 LCS = 1 이런식으로 표를 채워가준다. 중요한 것은 LCS가 하나 더 늘어나는 경우는 문자가 들어갈 수 있을 때 예를 들면 ACAYK 와 CAP 다음 순서에 ACAYKP 와 CAP가 나온다..

https://www.acmicpc.net/problem/1676 1676번: 팩토리얼 0의 개수 N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오. www.acmicpc.net 이 문제는 처음에 고민을 하다가 팩토리얼 숫자를 그리면서 규칙을 좀 살펴보니 5배수가 곱해질때마다 뒤에 0 이 붙는 것을 보고 이것을 이용해 풀었다. 왜냐하면 10이 곱해지려면 2와 5가 필요한데 2는 항상 5보다 많기 때문에 5가 몇개 있는지 세주면 된다. 주의 해야할 것은 5의 배수중 25 와 같이 5가 2번 곱해진것은 0이 2개가 추가 됨에 주의 해주면된다. 위 방법과 다이나믹 프로그래밍을 이용하여 하나씩 0의 개수를 저장하는데 5배수가 들어있는 수가 곱해지는 차례에는 i-5번..

https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 이 문제를 보고 bfs로 탐색을 하여 풀면 쉽게 풀릴거라고 생각해서 bfs로 풀어주었다. 풀고 난 후 힌트 부분쪽에는 다이나믹 프로그래밍이라고 되어있어서 다이나믹 프로그래밍으로도 풀고 두 개 방식 모두 정리해보았다. 첫번째 방식은 bfs로 푼 방식으로 처음에 딱 떠올라서 푼 방식이다. 입력 받은 n을 bfs에 넣어주면 bfs는 - 3으로 나눠지고 나눈수가 방문되어지지 않은 경우 큐에 넣어준다. - 2로 나눠지고 나눈수가 방문되어지지 않은 경우 큐에 넣어준다. - 1을 뺀 수가 방문되어지지 않은 경우 큐에 넣어준..