boj 2747, 1182, 11729

main.pdf

1.87MB

학교에서 친구들끼리 책을 읽고 활동을 하는 프로그램이 있어서
http://www.yes24.com/Product/Goods/79257722

다이내믹 프로그래밍 완전 정복 - YES24

다이내믹 프로그래밍 완전 정복이라는 책을 읽고, 직접 백준에서 1시간 30분 동안 문제를 푸는 활동을 했다.

내가 DP에 매우 약해서 골랐는데 정작 책은 잃어버리고, 문제 풀때는 하노이탑 푸느라 시간안에 DP까지 가지를 못했다.
그래도 하노이탑 푼게 뿌듯하다. 옛날에 시도했다가 못 풀었었는데, 아무래도 종이에다 뭐 써보면서 규칙 찾는게 중요한거 같다.

친구들한테 백준 광고하고 싶어서 이 책 고른것도 있었는데, 백준은 오프라인에서 다같이 모여서 풀어야 할 것 같다.
문제랑 책이랑 비교하면서 직접 풀는 그런 그림을 기대했는데 몇명은 그냥 인터넷 보고 베끼더라..

2747-피보나치 수

#include <cstdio> int n, fib[60]; int main() { scanf("%d", &n); fib[0] = 0, fib[1] = 1; for(int i = 2; i <= n; i++) { fib[i] = fib[i-1] + fib[i-2]; } printf("%d", fib[n]); }

11729-하노이 탑 이동 순서

#include <cstdio> #include <vector> int n; std::vector<std::pair<int, int>> ans; int move(int from, int to) { ans.push_back(std::make_pair(from, to)); return 0; } int mv(int cnt, int from, int to) { if(cnt == 1) return move(from, to); return mv(cnt - 1, from, 1^2^3^from^to) + mv(1, from, to) + mv(cnt-1, 1^2^3^from^to, to); } int main() { scanf("%d", &n); mv(n, 1, 3); printf("%d\n", ans.size()); for(int i = 0; i < ans.size(); i++) { printf("%d %d\n", ans[i].first, ans[i].second); } }

Deque를 사용하면 판 옮기는 것을 구현할 수 있다고 pdf에 써놨는데, 생각해보니 필요없는 코드라 지웠다.


1182-부분수열의 합

#include <cstdio> int n, s, a[30], cnt, tmp; bool b[30]; int plusOne(int pos, bool carry) { if(pos > n) return 0; bool tmp2 = b[pos]; b[pos] ^= true; if(tmp2&true) plusOne(pos+1, b[pos]&true); return 0; } bool check() { for(int i = 0; i < n; i++) { if(!b[i]) return false; } return true; } int main() { scanf("%d %d", &n, &s); for(int i = 0; i < n; i++) scanf("%d", &a[i]); plusOne(0, false); while(!check()) { tmp = 0; for(int i = 0; i < n; i++) tmp += b[i]*a[i]; if(tmp == s) cnt++; plusOne(0, false); } for(int i = 0; i < n; i++) tmp += b[i]*a[i]; if(tmp == s) cnt++; printf("%d\n", cnt); }