꾸준함

문제 링크입니다: https://www.acmicpc.net/problem/1006얼핏 보면 완전탐색법을 통해 쉽게 풀 수 있는 문제로 보이지만 사실 조건이 엄청 많은 문제였습니다.제가 풀었을 때는 무슨 이유인지 모르겠지만 계속 런타임 오류가 발생했습니다.그래서 다른 사람들의 코드를 참고해서 작성해보려고 했는데 우연히 들어가본 블로그에 너무나도 완벽한 코드가 있어서 그 코드에 주석을 추가해서 제 나름대로 해석해봤습니다.참고한 블로그 -> https://blog.naver.com/whgksdyd112/220956454574 /* 문제가 길기 때문에 생략 */ #include #include #include //memset using namespace std; const int MAX = 10000; int..

문제 링크입니다: https://www.acmicpc.net/problem/11727http://jaimemin.tistory.com/323와 비슷한 문제였습니다.2*2 타일이 추가되었으므로 밑변의 길이가 2인 경우를 2배하는 것이 핵심이였습니다. /* 2×n 직사각형을 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. */ #include #include //memset using namespace std; const int MOD = 10007; int N; int cache[1001]; //2*width 크기의 사각형을 채우는 방법의 수를 MOD로 나눈 나머지 반환 int tiling(int width) { //기저 사례:width가 1 이하일 때 if (width > N; ..

http://jaimemin.tistory.com/391?category=988050과 비슷한 문제입니다.두가지 다른 점은 다음과 같습니다.1. 백준 1931번 문제와 달리 한 회의의 소요시간은 1 이상이고2. 한 회의의 끝과 그 다음 회의의 시작은 동일할 수 없다는 점입니다.(이런 경우 겹친다고 여긴다.) 물론 탐욕법(greedy method)를 사용하면 쉽게 풀리지만 동적계획법을 연습 중이기 때문에 동적계획법으로도 풀어봤습니다. /* 회사에 회의실이 하나밖에 없는데, n(0; i--) for(int j=i-1; j>0; j--) if (meeting[i].start > meeting[j].end) { before[i] = j; break; } } int schedule(int idx) { if (id..

문제 링크입니다: https://www.acmicpc.net/problem/11052'(i-j)개 세트 팔았을 때 최대값 + j개 세트 가격' 이 부분이 핵심이였습니다. /* 강남역에서 붕어빵 장사를 하고 있는 해빈이는 지금 붕어빵이 N개 남았다. 해빈이는 적절히 붕어빵 세트 메뉴를 구성해서 붕어빵을 팔아서 얻을 수 있는 수익을 최대로 만드려고 한다. 붕어빵 세트 메뉴는 붕어빵을 묶어서 파는 것을 의미하고, 세트 메뉴의 가격은 이미 정해져 있다. 붕어빵 i개로 이루어진 세트 메뉴의 가격은 Pi 원이다. 붕어빵이 4개 남아 있고, 1개 팔 때의 가격이 1, 2개는 5, 3개는 6, 4개는 7인 경우에 해빈이가 얻을 수 있는 최대 수익은 10원이다. 2개, 2개로 붕어빵을 팔면 되기 때문이다. 1개 팔 때의..

문제 링크입니다: https://www.acmicpc.net/problem/1010이 문제의 핵심은 서쪽의 첫번째 사이트가 연결한 다리를 고정으로 놓고 부분문제로 나누는 것이였습니다.테스트 케이스를 입력 받고 그만큼 반복해서 답을 도출해야하기 때문에 미리 모든 경우의 수를 계산해놓고 결과를 출력하는 형식으로 코드를 작성했습니다. /* 강 주변에서 다리를 짓기에 적합한 곳을 사이트라고 한다. 재원이는 강 주변을 면밀히 조사해 본 결과 강의 서쪽에는 N개의 사이트가 있고 동쪽에는 M개의 사이트가 있다는 것을 알았다. (N ≤ M) 재원이는 서쪽의 사이트와 동쪽의 사이트를 다리로 연결하려고 한다. (이때 한 사이트에는 최대 한 개의 다리만 연결될 수 있다.) 재원이는 다리를 최대한 많이 지으려고 하기 때문에 ..

문제 링크입니다: https://www.acmicpc.net/problem/2193규칙을 찾다보면 피보나치 수열과 동일하다는 것을 알 수 있습니다.핵심은 캐시와 반환값을 long long으로 선언하는 것이였습니다. /* 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다.이친수는 다음의 성질을 만족한다. 1.이친수는 0으로 시작하지 않는다. 2. 이친수에서는 1이 두 번 연속으로 나타나지 않는다. 즉, 11을 부분 문자열로 갖지 않는다. 예를 들면 1, 10, 100, 101, 1000, 1001 등이 이친수가 된다.하지만 0010101이나 101101은 각각 1, 2번 규칙에 위배되므로 이친수가 아니다. N(1..

문제 링크입니다: https://algospot.com/judge/problem/read/GENIUS두니발 박사의 탈옥(http://jaimemin.tistory.com/335)과 유사한 문제였습니다.다른 점이라면 다음 곡이 나올 확률이 다르다는 점이였습니다.직관적으로 해석해서 프로그래밍을 하면 편하지만 K(시간)의 범위가 크기 때문에 시간초과가 발생합니다.따라서 피보나치 수열처럼 행렬을 사용하여 푸는 것이 핵심입니다. #include #include #include using namespace std; int songNum, K, length[50]; //곡 갯수, K분 후, 곡의 길이 double T[50][50]; //다음에 나올 곡 확률 class SquareMatrix { private: vec..

문제 링크입니다: https://www.acmicpc.net/problem/9095규칙을 찾기 위해 직접 나열한 결과 간단한 점화식을 얻을 수 있었습니다. /* 정수 4를 1, 2, 3의 조합으로 나타내는 방법은 총 7가지가 있다. 1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2, 1+3, 3+1 정수 n이 주어졌을 때, n을 1,2,3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오. */ #include using namespace std; int N; //주어진 정수 int cache[11]; //N test_case; for (int i = 0; i > N; cout

문제 링크입니다: https://algospot.com/judge/problem/read/SUSHI반복 동적계획법을 이용하여 푼 문제였습니다.예산의 범위가 int의 양의 정수 범위와 같으므로 매우 컸기 때문에 미리 100으로 나누는 것이 핵심이였습니다.책을 통해 슬라이딩 윈도우 기법을 처음 접했는데 상당히 유용한 것 같습니다. #include #include using namespace std; //직관적으로 풀었을 경우 MAX_BUDGET(너무 크다) //#define MAX_BUDGET 1000000000 const int MULTIPLIER = 100; int type, cash; //스시의 종류와 갖고 있는 예산 int price[20], preference[20]; //가격과 선호도 //int ..

문제 링크입니다: https://algospot.com/judge/problem/read/TRIANGLEPATHhttp://jaimemin.tistory.com/316에서 동일한 문제를 풀었지만 이번에는 재귀함수가 아닌 반복 동적 계획법을 이용해 문제를 풀었습니다.그 결과, 재귀함수를 사용했을 때보다 실행속도가 빨라진 것을 확인할 수 있었습니다. /*삼각형으로 배치된 자연수들이 있다.(정사각을 왼쪽 위에서 오른쪽 아래 대각선 기준으로 잘랐을 때 아래 부분)맨 위의 숫자에서 시작해서, 한번에 한 칸씩 아래로 내려가맨 아래 줄까지 닿는 경로를 만들려고 한다.경로는 아래줄로 내려갈 때마다 바로 아래 숫자 혹은 오른쪽 아래 숫자로 내려갈 수 있다.이 때 모든 경로 중 숫자의 합을 최대화하는 경로는?또한 경로에 ..