문제 https://www.acmicpc.net/problem/11727 풀이 취준생 때 이해하기 힘들어서 포기했던 문제다. 시간을 두고 천천히 그림을 그려가면서 생각해보면 점화식을 생각해낼 수 있습니다. 2x2 타일을 채우는 경우를 그림으로 그려보고, 2x3 을 채우는 방식을 생각해봅니다. 2x3은 앞 쪽에 2x1 타일을 채우고 나머지를 채우는 경우와 뒤 쪽에 2x1을 채우고 나머지를 채우는 경우로 생각 할 수 있습니다. 소스코드 // boj.kr/11727 // 2xn 타일링 #include using namespace std; #define MOD 10007 const int MAX_N = 1000; long long gCache[MAX_N+1]; int main(){ ios::sync_with_s..
문제 https://www.acmicpc.net/problem/1563 풀이 dynamic programming / recursion 을 통해 풀이 했습니다. gCache : day 에 출석, 지각, 결석 횟수 저장 recursion 함수를 통해 저장된 값이 있으면 활용하고 아닌 경우 다음날을 3가지 경우로 분기시켜 진행 시켰습니다. 출석하는 경우 (day + 1, attendance + 1, late, 0) ㄴ지각하는 경우 (day + 1, attendance, late +1, 0) 결석하는 경우 (day +1, attendance, late, absent+1) 소스코드 #include #include using namespace std; const int MAX_N = 1000 + 1; const i..
문제https://www.acmicpc.net/problem/15686풀이과정Dfs와 백트래킹을 통한 완전탐색으로 구현을 했습니다.M개의 치킨집을 골랐을 경우 최소거리의 합을 구하고 가장 작은 경우만 저장해서 출력했습니다.DFS와 백트래킹을 통한 완전탐색 문제를 풀어봤다면 푸실 수 있을 것 같습니다. 알고리즘 1(집), 2(치킨집) 일 경우 각각 person, chicken 벡터에 위치를 저장합니다. 재귀함수를 통해 M개의 치킨집을 선택합니다 person 벡터를 돌며 집과 선택된 치킨집의 거리 중 최소값만을 더합니다. 치킨집 M개를 뽑는 모든 경우를 탐색하고 최소거리의 합 중 가장 작은 값만 저장합니다. 소스코드#include #include #include using namespace std; #def..