[백준] 1932번 정수 삼각형 - C++ (dp, bottom-up)
2022. 10. 8. 01:05
solving/C, C++
발상 너무 길어서 잘 짠 코드는 아닌 거 같지만.. 그래도 풀이를 남겨본다. 우선 이차원 배열을 써야겠다고 생각함 (삼각형 형태니까) dp와 주어진 값을 받는 배열 모두 이차원 배열로 선언했다. dp[i][j]에 대한 점화식은 세가지 경우로 나뉜다. 1) j>1이고 j> N; int dp[N+1][N+1]; int route[N+1][N+1]; for(int i=1; i route[i][j]; } } vector ans; for(int i=1; i
[백준] 1463번 1로 만들기 - C++ (dp-동적계획법, bottom-up 반복문)
2022. 10. 7. 22:34
solving/C, C++
발상 우선 dp 사용 시 고려해야 할 점 - 부분해가 최적해의 일부분인가? 와 점화식이 존재하는가? 를 고려했을 때, dp[i] 는 dp[i-1], dp[i/3], dp[i/2] 중의 최솟값에 +1 (이 경우들에서 한 단계만 더 연산하면 답을 구할 수 있으므로) 를 더해주면 된다는 점에서 dp를 사용해서 푸는 문제임을 알 수 있다. 우선 메모이제이션할 배열 dp를 선언해 준다. 여기서는 따로 함수를 만들지 않고 main함수 안에서 모두 해결하였으므로 배열의 크기를 N으로 선언한다. 위에서 언급했듯이, dp[i] 의 최적해에는 3가지 경우가 존재한다. 1. dp[i-1] + 1 (1을 뺄 수 있으므로) 2. dp[i/2] (2로 나눌 수 있으므로. i가 2로 나누어지는 경우에만 성립한다.) 2. dp[i/..
[백준] 11659번 구간 합 구하기 4 - C++ (동적계획법)
2022. 10. 3. 23:12
solving/C, C++
발상 1. 우선 메모이제이션할 배열 dp와 숫자를 받을 배열 array를 선언한다. 2. 각 dp[i] 에는 1부터 i까지의 합을 저장한다. 3. sum 함수를 이용해 합을 구한다. 이 때, dp[i] 가 저장되어 있으면 (-1이 아니라면) dp[i] 값을 불러오도록 하고, 저장되어 있지 않으면 dp[i] 값을 새로 구한다. dp[0]일 경우 0을. 아닐 경우 sum[k-1]에 arr[k-1] 값을 더한 것을 return한다. (k-1인 이유는 index의 숫자가 하나 작기 때문) 소스코드 #include int dp [100001]; int arr[100001]; int sum (int k){ if (dp[k] != -1) return dp[k]; if (k == 0) dp[k] = 0; else dp..
[백준] 1027번 고층 건물 - C++ (Bruteforce)
2022. 10. 3. 14:37
solving/C, C++
문제요약 문제에서 N과 N개만큼의 건물 높이가 주어진다. i번째 빌딩은 (i, 0) 부터 (i, 높이) 까지의 선분으로 나타낸다. 이 때 건물 A에서 건물 B를 볼 수 있으려면, 그 사이에 A-B를 잇는 선분에 닿는 건물이 없으면 된다. 빌딩에서 보이는 건물 수의 최댓값을 출력하면 된다. 풀이방법 1. 건물의 기울기를 계산해 비교하는 방식으로 문제를 해결하고자 했다. 2. 건물 A를 기준으로 for문을 이용해 A 오른쪽에 있는 모든 건물의 기울기를 계산해나가며 최댓값을 갱신한다. (초기 최댓값은 문제에서 가능한 범위보다 작게 설정한다.) 3. 건물 A에서 B가 보이는지를 판단하고자 할 때, 현재 최댓값은 A에서 B-1까지의 건물을 이은 선분 기울기의 최댓값이다. 이 값보다 A-B 선분의 기울기가 크다면,..
[백준] 1524번 세준세비 - C++ (Stack)
2022. 10. 1. 23:10
solving/C, C++
발상 1달 전에 구현으로 낑낑대다가 결국 못 풀고 넘겼던 문제.. 문득 stack을 이용하면 풀 수 있을 것 같다는 생각이 들어, stack을 이용해 구현해 보았다. 문제의 조건을 보면 가장 약한 병사가 죽는다. - 가장 약한 병사가 둘일 때 한쪽에 있다면 둘 중 하나가 죽는다. - 양쪽에 있다면 세비의 병사가 죽는다. 이 부분이 포인트이다. 우선 주어진 병사들을 내림차순으로 정렬하고, stack에 하나씩 넣은 뒤 top을 비교하면 가장 약한 병사를 찾을 수 있을 것이다. 1. 세준이의 병사가 가장 약하다 (sejuns.top() sebis.top()) : s..
[백준] 15650번 N과 M(2) - C++
2022. 9. 27. 00:10
solving/C, C++
소스코드 #include #include #include using namespace std; int arr[8]; int selected[8]; int N, M; void recur(int selCnt, int idx){ if (idx == N+1) return; if (selCnt == M){ for(int j = 0; j < selCnt; j++){ cout M; for (int i=0; i
[백준] 2493번 탑 - C++
2022. 9. 24. 22:42
solving/C, C++
소스코드 #include #include #include using namespace std; int main(){ stack st; int N; scanf("%d", &N); int temp, i; for(i=1; i temp){ printf("%d ", st.top().second); break; } st.pop(); } if(st.empty() == true) { printf("0 "); } st.push(make_pair(temp, i)); } } 스택을 사용해야 하는 것 같기는 했지만 (한쪽에서만 pop, push 발생) 발상이 어려웠기에 검색을 참고했다. 추후에 스스로의 힘으로 다시 풀어보야아 할 듯.. 해설 우선 stack 하나만을 사용하였고, pair 자료형을 이용해 하나의 stack만 사..
[백준] 1018 체스판 다시 칠하기 - C++ (Bruteforece, 완전탐색)
2022. 9. 21. 00:59
solving/C, C++
소스코드 #include using namespace std; int main(){ int A, B; cin >> A >> B; int alast = A-8; int blast = B-8; int i, j, k, l; char chess[A+1][B+1]; for (i=0; i> chess[i]; } int min = 65; for (i=0; i