본문 바로가기

프로그래머스/동적계획법

 (10)
3xn 타일링 - Level4 programmers.co.kr/learn/courses/30/lessons/12902 코딩테스트 연습 - 3 x n 타일링 programmers.co.kr #include #include #include #define MODULER 1000000007; using namespace std; int solution(int n) { int answer = 0; long long dp[5001]; if(n%2==1){return 0;} memset(dp,0,sizeof(dp)); dp[0]=1; dp[2]=3; //점화식 이용 //F[N] = F[N - 2] * F[2] + F[N - 4] * 2 + F[N - 6] * 2 + ... + F[2] * 2 + 2 for(int i=4; i=0; j= j-2){..
스티커모으기2 programmers.co.kr/learn/courses/30/lessons/12971 코딩테스트 연습 - 스티커 모으기(2) N개의 스티커가 원형으로 연결되어 있습니다. 다음 그림은 N = 8인 경우의 예시입니다. 원형으로 연결된 스티커에서 몇 장의 스티커를 뜯어내어 뜯어낸 스티커에 적힌 숫자의 합이 최대가 되도록 programmers.co.kr #include #include #include using namespace std; bool check[100000]={false,}; int maxnum =0; int dp[100000]; int dp2[100000]; int solution(vector sticker) { int answer = 36; if(sticker.size()==1){return ..
거스름돈 programmers.co.kr/learn/courses/30/lessons/12907 코딩테스트 연습 - 거스름돈 Finn은 편의점에서 야간 아르바이트를 하고 있습니다. 야간에 손님이 너무 없어 심심한 Finn은 손님들께 거스름돈을 n 원을 줄 때 방법의 경우의 수를 구하기로 하였습니다. 예를 들어서 손님께 5 programmers.co.kr #include #include using namespace std; long long d[111111]; int solution(int n, vector money) { int answer = 0; d[0] = 1; // for (int i=money[0] ; i
보행자 천국 programmers.co.kr/learn/courses/30/lessons/1832 코딩테스트 연습 - 보행자 천국 3 3 [[0, 0, 0], [0, 0, 0], [0, 0, 0]] 6 3 6 [[0, 2, 0, 0, 0, 2], [0, 0, 2, 0, 1, 0], [1, 0, 0, 2, 2, 0]] 2 programmers.co.kr 처음에는 밑에와 같이 DFS로 풀었더니 시간초과가 났다 그때서야 이문제가 DFS로 푸는 문제가 아니라는 것을 알게 되었다 #include #include #include using namespace std; int MOD = 20170805; int dx[] = {1,0}; //아래 int dy[] = {0,1}; //오른쪽 int count; void dfs(vect..
가장 긴 팰린드롬 programmers.co.kr/learn/courses/30/lessons/12904 코딩테스트 연습 - 가장 긴 팰린드롬 앞뒤를 뒤집어도 똑같은 문자열을 팰린드롬(palindrome)이라고 합니다. 문자열 s가 주어질 때, s의 부분문자열(Substring)중 가장 긴 팰린드롬의 길이를 return 하는 solution 함수를 완성해 주세요. 예를들 programmers.co.kr #include #include #include using namespace std; int solution(string s) { int answer=1; int n = s.size(); vectorcheck(n,vector(n,false)); for(int i=0; i
풍선 터트리기 programmers.co.kr/learn/courses/30/lessons/68646 코딩테스트 연습 - 풍선 터트리기 [-16,27,65,-2,58,-92,-71,-68,-61,-33] 6 programmers.co.kr #include #include #include using namespace std; int solution(vector a) { int answer =0; int sz = a.size(); vectorleftmin(sz); vectorrightmin(sz); int minnum = 1000000000; for(int i=0; i
등굣길 programmers.co.kr/learn/courses/30/lessons/42898 코딩테스트 연습 - 등굣길 계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다. 아래 그림은 m = programmers.co.kr #include #include #include using namespace std; int solution(int m, int n, vector puddles) { int answer = 0; int map[105][105] = {0,}; for(int j=1; j
정수 삼각형 programmers.co.kr/learn/courses/30/lessons/43105 코딩테스트 연습 - 정수 삼각형 [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]] 30 programmers.co.kr #include #include #include #include using namespace std; int solution(vector triangle) { int answer = 0; int n = triangle.size(); int check[500][500]; memset(check,0,sizeof(check)); check[0][0] = triangle[0][0]; for(int i=1; i

티스토리툴바