김머성 블로그

[BAE/<JOON> 문제풀이] 2631. 줄세우기 (DP.050)

https://www.acmicpc.net/problem/2631 2631번: 줄세우기 KOI 어린이집에는 N명의 아이들이 있다. 오늘은 소풍을 가는 날이다. 선생님은 1번부터 N번까지 번호가 적혀있는 번호표를 아이들의 가슴에 붙여주었다. 선생님은 아이들을 효과적으로 보호하기 www.acmicpc.net LIS를 통해 이미 정렬된 애들은 빼고 나머지 애들만 정렬하는 코드를 사용했다. LIS짤 때마다 동적 테이블 1로 초기화하는걸 안해서 시간이 오래걸린다. 웰논 알고리즘들을 언제 한번 정형화해서 외우든지 해야겠다. 물론 원리를 외우는게 맞긴 한데 문제 풀 때는 그냥 외워서 쓰는게 나을거같다. 문제 풀 때마다 원리 생각해서 짜면 너무 느림.. 더보기 #include #include using namespac..

[BAE/<JOON> 문제풀이] 9507.Generations of Tribbles (DP.049)

https://www.acmicpc.net/problem/9507 9507번: Generations of Tribbles 문제 꿍은 군대에서 진짜 할짓이 없다. 그래서 꿍만의 피보나치를 만들어보려고 한다. 기존의 피보나치는 너무 단순해서 꿍은 좀더 복잡한 피보나치를 만들어보고자 한다. 그래서 다음과 같은 � www.acmicpc.net 더보기 #include #include #include using namespace std; string add(string& a, string& b) { int l1 = a.length(); int l2 = b.length(); string s; string l; if(l1 == l2) { s = a; l = b; } else { s = l1 < l2 ? a : b; l..

[BAE/<JOON> 문제풀이] 10164. 격자상 경로 (DP.048)

https://www.acmicpc.net/problem/10164 10164번: 격자상의 경로 입력의 첫째 줄에는 격자의 행의 수와 열의 수를 나타내는 두 정수 N과 M(1 ≤ N, M ≤ 15), 그리고 ○로 표시된 칸의 번호를 나타내는 정수 K(K=0 또는 1 > n >> m; dp.resize(n + 1); dp[0].resize(m + 1); for (int i = 1; i > k; int dx, dy; if (k == 0) { dx = n; dy = m; }..

[BAE/<JOON> 문제풀이] 5557. 1학년 (DP.047)

https://www.acmicpc.net/problem/5557 5557번: 1학년 문제 상근이가 1학년 때, 덧셈, 뺄셈을 매우 좋아했다. 상근이는 숫자가 줄 지어있는 것을 보기만 하면, 마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 사이에는 '+' 또는 '-'를 넣어 등식을 만들�� www.acmicpc.net 더보기 #include #include using namespace std; int main() { int n; cin >> n; vector arr; unsigned long long prevv[101][21]; arr.resize(n + 1); for (int i = 1; i > arr[i]; } for (int j = 0; j

[BAE/<JOON> 문제풀이] 11049. 행렬 곱셈 순서 (DP.046)

https://www.acmicpc.net/problem/11049 11049번: 행렬 곱셈 순서 첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같� www.acmicpc.net 전에 풀었던 소설가 문제랑 거의 같은 문제였다. 비슷한 유형의 문제들이 있는걸 보니 이런 종류 문제를 푸는 정형화된 방법이 따로있는 것 같다. 더보기 #include #include #include using namespace std; struct met { int x, y; unsigned long sum = 1; }; met power(met a, met b) { if (a.y ..

[BAE/<JOON> 문제풀이] 10942. 팰린드롬? (DP.045)

https://www.acmicpc.net/problem/10942 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net 각각의 팰린드롬이 시작하는 위치 / 끝나는 위치를 DP배열에 저장하면서 탐색을 한다. 사실 그냥 일반적인 메모이제이션 문제같다. 더보기 #define _CRT_SECURE_NO_WARNINGS #include #include using namespace std; int n; vector arr; vector dp; int is_phalindrom(int s, int e) { if (s == e) return 1; int tsize = ..