꾸준함

문제 링크입니다: https://www.acmicpc.net/problem/1699처음에 안일하게 생각했다가 틀린 문제였습니다.틀린 코드와 맞은 코드를 비교하면 쉽게 이해할 수 있는 문제입니다.우선 틀린 코드입니다./* 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다. 이 경우, 수학자 숌크라테스는 “11은 3개 항의 제곱수 합으로 표현할 수 있다.”라고 말한다. 또한 11은 그보다 적은 항의 제곱수 합으로 표현할 수 없으므로, 11을 그 합으로써 표현할 수 있는 제곱수 항의 최소 개수는 3이다. 주어진 자연수 N을 이렇게..

문제 링크입니다: https://www.acmicpc.net/problem/2294백준 2293번 동전 1(http://jaimemin.tistory.com/362)과 유사한 문제였습니다. /* n가지 종류의 동전이 있다. 각각의 동전이 나타내는 가치는 다르다. 이 동전들을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그러면서 동전의 개수가 최소가 되도록 하려고 한다. (각각의 동전은 몇개라도 사용할 수 있다.) */ #include #include #include //memset using namespace std; const int MAX = 10000 + 1; int coinNum, total; //동전 갯수, 총합 int coinValue[101], cache[MAX]; int m..

문제 링크입니다: 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/11047가치가 큰 동전부터 더해나가는 것이 핵심이였습니다. /* 준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다. 동전을 적절히 사용해서 그 가치의 합을 K로 만드려고 한다. 이 때 필요한 동전 개수의 최소값을 구하는 프로그램을 작성하시오. */ #include #include using namespace std; int N; //동전 수 int total; //총합 vector v; int minCoin(void) { int cnt = 0; for(int i=v.size()-1; i>=0; i--) //가치가 큰 동전부터 빼야 최소 반환 while (total - v[i] >= 0) { tota..

문제 링크입니다: 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; ..

문제 링크입니다: https://www.acmicpc.net/problem/4587codewars의 Some Egyptian fractions(http://jaimemin.tistory.com/395?category=987931) 문제를 푼 다음 비슷한 문제가 있어서 풀어봤습니다.직접 테스트 케이스를 입력하고 컴파일을 하면 맞게 나오는데 어디가 틀린건지 도무지 모르겠습니다.혹시 틀린 부분이 있다면 댓글을 통해 알려주시면 정말 감사하겠습니다! #include #include #include using namespace std; const int MAX = 1000000; vector v; //최대공약수long long int gcd(long long int N, long long int D) //great..

문제 링크입니다: https://www.acmicpc.net/problem/1931탐욕법(greedy method)을 이용하여 푸는 문제였습니다. /* 한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의들에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 최대수의 회의를 찾아라. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다. */ #include #include #include using namespace std; int N..

문제 링크입니다: 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..