김머성 블로그

[BAE/<JOON> 문제풀이] 5582. 로봇 조종하기

https://www.acmicpc.net/problem/2169 2169번: 로봇 조종하기 첫째 줄에 N, M(1≤N, M≤1,000)이 주어진다. 다음 N개의 줄에는 M개의 수로 배열이 주어진다. 배열의 각 수는 절댓값이 100을 넘지 않는 정수이다. 이 값은 그 지역의 가치를 나타낸다. www.acmicpc.net 문제 티어가 골드1인거보고 무서웠는데 그냥 웰논 알고리즘 적용하면 풀리는 문제였다. 당황스럽다. 더보기 #include #include #include using namespace std; int main() { int n, m; cin >> n >> m; vector arr, dp, dp2; arr.resize(n + 1); dp.resize(n + 1); dp2.resize(n + 1..

[BAE/<JOON> 문제풀이] 2352. 반도체 설계

https://www.acmicpc.net/problem/2352 2352번: 반도체 설계 첫째 줄에 정수 n(1 ≤ n ≤ 40,000)이 주어진다. 다음 줄에는 차례로 1번 포트와 연결되어야 하는 포트 번호, 2번 포트와 연결되어야 하는 포트 번호, …, n번 포트와 연결되어야 하는 포트 번호가 주 www.acmicpc.net 평범한 증가수열 문제인줄 알았는데 일반적인 N^2 해법으로는 안풀리고 더 최적화된 방법을 사용해야한다. 일반적인 증가수열의 해법을 복기해보자. 각 수열의 인덱스마다 그 지점까지의 최장 증가수열 길이를 저장해놓고 현재 지점과 이전 지점을 비교하여 증가 수열이라면 값을 갱신하는 식으로 최장증가수열의 길이를 구했다. 즉, 각각의 지점들에 대해 이전 지점들을 모두 비교하므로 시간 복잡..

[BAE/<JOON> 문제풀이] 1038. 감소하는 수

https://www.acmicpc.net/problem/1038 1038번: 감소하는 수 음이 아닌 정수 X의 자릿수가 가장 큰 자릿수부터 작은 자릿수까지 감소한다면, 그 수를 감소하는 수라고 한다. 예를 들어, 321과 950은 감소하는 수지만, 322와 958은 아니다. N번째 감소하는 수를 �� www.acmicpc.net 최댓값을 987654321로 생각하고 풀었다. 아무리 해도 안되길래 질문 내용보고 9876543210 인걸 알았다. 능지 더보기 #include #include using namespace std; int main() { int n; cin >> n; if (n < 10) { cout

[BAE/<JOON> 문제풀이] 9084. 동전

https://www.acmicpc.net/problem/9084 9084번: 동전 우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 예를 들어, 30원을 만들기 위해서는 www.acmicpc.net 더보기 #include #include using namespace std; int main() { int tc; cin >> tc; while (tc--) { int n, m; cin >> n; vector coin; vector dp; coin.resize(n + 1); dp.resize(n + 1); for (int i = 1; i > coin[i]; } cin >> m; f..

[BAE/<JOON> 문제풀이] 11060. 점프점프

https://www.acmicpc.net/problem/11060 11060번: 점프 점프 재환이가 1×N 크기의 미로에 갇혀있다. 미로는 1×1 크기의 칸으로 이루어져 있고, 각 칸에는 정수가 하나 쓰여 있다. i번째 칸에 쓰여 있는 수를 Ai라고 했을 때, 재환이는 Ai이하만큼 오른쪽으로 � www.acmicpc.net 더보기 #include #include #include using namespace std; int main() { vector arr, dp; int n; cin >> n; arr.resize(n + 1); dp.resize(n + 1); for (int i = 1; i > arr[i]; } dp[1] = 0; for (int i = 2; i = i) { dp[i] = min(dp..

[BAE/<JOON> 문제풀이] 2302. 극장좌석

https://www.acmicpc.net/problem/2302 2302번: 극장 좌석 주어진 조건을 만족하면서 사람들이 좌석에 앉을 수 있는 방법의 가짓수를 출력한다. 방법의 가짓수는 2,000,000,000을 넘지 않는다. (2,000,000,000 > n >> m; vector dp; vector arr; arr.resize(m + 2); dp.resize(n + 1); for (int i = 1; i > arr[i]; } int s = 2; int d = 1; for (int i = 0; i