C++

#문제 간단 정리 dp 를 사용해서 풀어야한다 #문제 해결 방법 문제 상황 먼저, 문제 상황을 이해해야 합니다. 여기서는 가로로 2칸, 세로로 N칸인 우리가 있고, 사자들을 배치하는 문제입니다. 조건은 다음과 같습니다: 사자들은 가로나 세로로 붙어 있을 수 없습니다. 사자를 한 마리도 배치하지 않는 경우도 포함합니다. 동적 프로그래밍 이해하기 DP는 큰 문제를 작은 문제로 나누어 푸는 방법입니다. 이 문제에서는 'N번째 칸까지 사자를 어떻게 배치할 수 있는가'를 작은 문제로 삼습니다. 각 칸에 대해 다음과 같은 세 가지 경우를 생각해볼 수 있습니다: 사자를 배치하지 않는 경우. 사자를 첫 번째 칸에만 배치하는 경우. 사자를 두 번째 칸에만 배치하는 경우. DP 배열 설정 DP를 사용하기 위해 각 상태를 ..

https://www.acmicpc.net/problem/15961 15961번: 회전 초밥 첫 번째 줄에는 회전 초밥 벨트에 놓인 접시의 수 N, 초밥의 가짓수 d, 연속해서 먹는 접시의 수 k, 쿠폰 번호 c가 각각 하나의 빈 칸을 사이에 두고 주어진다. 단, 2 ≤ N ≤ 3,000,000, 2 ≤ d ≤ 3,000, 2 www.acmicpc.net #문제 해결 방법 슬라이딩 윈도우를 사용하자 #전체 코드 #include #include using namespace std; int main() { int N, d, k, c; cin >> N >> d >> k >> c; vector sushi(N); vector sushiCount(d + 1, 0); for (int i = 0; i < N; i++)..

https://www.acmicpc.net/problem/16472 16472번: 고냥이 고양이는 너무 귀엽다. 사람들은 고양이를 너무 귀여워했고, 결국 고양이와 더욱 가까워지고 싶어 고양이와의 소통을 위한 고양이 말 번역기를 발명하기로 했다. 이 번역기는 사람의 언어를 고 www.acmicpc.net #문제 해결 방법 투 포인터를 사용하자 #전체 코드 #include #include using namespace std; int main() { int n; cin >> n; string s; cin >> s; int st = 0, en = 0; int maxLength = 0; int curType = 0; int alpha[26] = { 0, }; while (en < s.length()) { if (..

https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 이 문제는 Dynamic Programming (DP)을 사용하여 해결할 수 있는 문제입니다. 가장 긴 증가하는 부분 수열(Longest Increasing Subsequence, LIS)를 찾는 문제입니다. #발상 주어진 수열 A에서, 각 위치에서 그 위치를 마지막으로 하는 가장 긴 증가하는 부분 수열의 길이를 찾아보..

https://www.acmicpc.net/problem/16194 16194번: 카드 구매하기 2 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net #문제 간단 정리 dp 를 쓰자 주의할건 dp 배열의 초기값을 높게 설정해 줘야 한다 최소값을 고르는거기 때문에 0이 설정되어 있다면 최소값으로 0이 선택되기 때문이다. #전체 코드 #include #include #include using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; vector c..

https://www.acmicpc.net/problem/1068 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net #전체 코드 #include #include #include using namespace std; vector tree[51]; int check[51]; int leaf = 0; int wither; int root; void findLeaf(int node ) { check[node] = true; if (node == wither) return; bool isLeaf = true; fo..

https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net #문제 간단 정리 문제 풀이 전략 문제의 목적은 주어진 규칙에 따라 연속된 집들을 서로 다른 색으로 칠하는 최소 비용을 찾는 것입니다. 이러한 유형의 문제는 동적 프로그래밍(dynamic programming, DP)을 사용하여 해결할 수 있습니다. 문제를 해결하는 전략은 다음과 같습니다: 먼저, 각 집을 칠할 때의 비용을 2차원 배열에 저장합니다. 그런 다음, 다른 색상 조..

https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net #전체 코드 #include #include using namespace std; int main() { string A, B; cin >> A >> B; int ans = 0; int B_index = B.length() - 1; for (int i = A.length()-1; i >= 0; i--) { if (A[i] == B[B_index]) { B_index --; } else ans++; } sort(A.be..

https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net #문제 간단 정리 이 문제는 주어진 토마토의 상태에 따라 모든 토마토가 익게 되는 최소 일수를 찾는 문제입니다. 문제에서 요구하는 답을 찾기 위해 BFS(Breadth-First Search) 탐색 알고리즘을 사용합니다. #전체 코드 #include #include using namespace std; int a[1000][1000]; int d[1000][1000]; int dx..

https://www.acmicpc.net/problem/7562 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net #문제 간단 정리 체스판 위에서 나이트가 이동하는 최소 횟수를 계산하는 문제를 해결하기 위한 코드입니다. 코드는 입력으로 주어지는 테스트 케이스를 처리하고, 각 테스트 케이스에 대해 나이트가 최소 몇 번 움직여야 하는지를 출력합니다. 코드는 너비 우선 탐색(BFS)을 사용하여 문제를 해결합니다 #전체 코드 #include #include using namespace std; int dx[] = { ..