본문 바로가기

분류 전체보기108

[11055]가장 큰 증가하는 부분 수열- C++ https://www.acmicpc.net/problem/11055 11055번: 가장 큰 증가하는 부분 수열 수열 A가 주어졌을 때, 그 수열의 증가하는 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가하는 www.acmicpc.net 나에게는 정말 어려웠던 문제다 1시간 정도 고민하고 감도 잡히질 않아 답을 보았다. 풀이 배열 두 개를 만든다. 원본 배열, 테이블이다. int arr[1005]; int dp[1005]; 답에서는 한 번씩 다 돌아가면서 체크하는 방식을 알려줬다. 그림으로 설명해보겠다 이중 for문을 사용하여 i에 대하여 나보다 작은 수이면 더하고 본다.. 2023. 6. 6.
[5904]Moo 게임 - c++ 첫 번째 아이디어 일단 기본적인 재귀 형태로 풀려고 시도했다. 당연히 안될 걸 알고 있었지만 일단 시도 했으며 결과는 당연히 메모리 초과 CODE //Moo 게임 #include using namespace std; void init(){ ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); } //횟수 int n; int tot = 0; bool isFine = false; void isMoo(bool m2o){ //true = m, false = o if(m2o && tot == n){ cout n; moo(n/2); return 0; } 이렇게 해본 후 문제점이 뭔지를 찾아 나갔다. 1. 재귀를 몇번 반복해야 하는 가를 알려줘야 한다. 2. 그저 .. 2023. 6. 6.
1932 - c++ https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 시행 착오 최근에 다이나믹 프로그래밍 문제를 풀때 테이블이나 재귀식이 새각나지 않는 다면 브루트 포스 또는 모든 것을 다 검사하는 방식으로 코드를 짜보고 거기서 추가 적으로 재귀를 짜라는 식의 설명을 들은 적이 있다. 그리하여 나는 일단 DFS를 사용하여 모든 경우의 수를 다 구하였으며, 결과는 시간 초과 였으며 당연한 결과라 생각해 다이내믹 프로그래밍으로 짜보려고 노력했다. CODE #include using namespace std; void init(){ ios_.. 2023. 6. 4.
1463 - c++ 요약 1. 3으로 나누어 떨어지면 3으로 나누거나 2. 2로 나누어 떨어지면 2로 나누거나 3. 1을 빼거나 해서 4. 어떻게 해야 가장 빨리, 입력받은 N을 1로 만들 수 있는가? 아이디어 들어가기에 앞서 나의 첫 다이나믹 프로그래밍 문제이다. 답을 보고 풀었다. 강의에서는 먼저 테이블을 정의한다음 점화식을 찾았다. 테이블 정의 이 문제의 테이블은 D[i] = i 각 숫자에 대응되는 인덱스를 테이블로 만들 수 있을 것 같다 점화식 d[12] = d[12/4], d[12/2], d[12-1] d[3] = d[3/3], d[3-1] d[6] = d[6/3], d[6/2], d[6-1] d[11] = d[11-1] 이런식으로 점화식을 만들 수 있을 것 같다. 하지만 나 혼자 풀어 볼 때 무조건 재귀를 쓰겠지.. 2023. 6. 1.
14923 - c++ https://www.acmicpc.net/problem/14923 14923번: 미로 탈출 홍익이는 사악한 마법사의 꾐에 속아 N x M 미로 (Hx, Hy) 위치에 떨어졌다. 다행히도 홍익이는 마법사가 만든 미로의 탈출 위치(Ex, Ey)를 알고 있다. 하지만 미로에는 곳곳에 마법사가 설치한 벽이 www.acmicpc.net 요약 1. 현재 나의 위치와 탈출가능한 위치가 있다 2. 벽을 딱 한번 부술 수 있다. 벽을 부수고 최단 경로를 구하는 것 아이디어 예전에 비슷한 문제를 풀었던 적이 있다. 벽을 부순 상태일 때의 배열을 따로 만드는 방법으로 풀었던 기억이 있다. 그것과 비슷하게 dist [n][m][2]라는 배열을 만들고 dist[a][b][0] // 벽을 부수지 않은 상태 dist[a][b][.. 2023. 6. 1.
10825 - c++ 요약 1. 국어는 내림차순 2. 국어점수각 같다면 영어는 오름차순 3. 국, 영이 같다면 수학은 내림차순 4. 모두 같다면 이름은 사전순 문제를 풀며 솔직히 어려운 문제는 아니었다 정말 쉬운 문제 였다, 그런데도 글을 쓰는 이유는 답을 맞추고 다른 사람의 코드를 보는데 정말 창의 적인 아이디어를 보았기 때문이다. 이걸 글로 쓰지 않으면 바보 라는 생각이 들어 내 손이 저절로 움직였다. 그럼 풀이를 시작하겠다. 처음 나의 코드 #include using namespace std; void init(){ ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); } int n; bool cmp(const tuple &a, const tuple &b){ int a.. 2023. 6. 1.

티스토리툴바