꾸준함

문제 링크입니다: https://www.acmicpc.net/problem/2482 N개의 색 중 한개의 색을 고르는 경우의 수는 N가지 경우의 수입니다.두개 이상 색을 고르는 경우는 해당 색을 고르는 경우와 해당 색을 고르지 않는 경우로 나누어 생각하면 됩니다. #include #include //memset using namespace std; const int MAX = 1000 + 1; const int MOD = 1000000003; int N, K; long long cache[MAX][MAX]; void preCalculate(void) { //N>=4이므로 N=1, 2, 3에 대해 색상 하나 선택할 경우 미리 정의 for (int i = 1; i > K; preCalculate(); cout

문제 링크입니다: https://www.acmicpc.net/problem/1753 작년 자료구조 시간에 배운 다익스트라(Dijkstra) 알고리즘을 복습하기 위해 풀어본 문제였습니다.다익스트라 알고리즘은 시작점을 기준으로 인접한 노드들을 방문하며 시작점에서 해당 노드까지의 최소 거리를 찾는 알고리즘입니다.인접한 노드들을 방문한 뒤에는 인접한 노드들의 인접한 노드들을 확인하는 방식으로 작동합니다.한가지 주의할 점은 인접한 노드들을 방문할 때 비용이 최소인 노드부터 방문하므로 우선순위 큐에 비용을 음수 처리하여 넣어야한다는 점입니다.Priority Queue는 기본적으로 값의 크기대로 우선순위를 부여하기 때문에 위와 같이 처리해야합니다.물론, 우선순위 큐를 선언할 때 원하는 규칙을 설정해준다면 보다 직관적..

문제 링크입니다: https://www.acmicpc.net/problem/14954 개인적으로 문제 의역자연수 n에 대한 함수 f 정의: f(n)은 각 자리수의 제곱을 합한 결과를 반환한다.예를 들어 n=19이면 1^2+9^2=82이다.f 함수를 재귀적으로 호출했을 떄, 결과가 1이 출력되면 happy 숫자이다.하지만, unhappy 숫자는 재귀적으로 호출했음에도 불구하고 결국 1이 출력되지 않는다.unhappy 숫자의 대표적 예는 5이다. n이 주어졌을 때 happy 숫자인지 unhappy 숫자인지 판별하시오. #include #include using namespace std; vector v; void happyNumber(int N) { //기저 사례: 1이 나오면 HAPPY if (N == 1..

문제 링크입니다: https://www.acmicpc.net/problem/14753 개인적으로 문제 의역숫자가 적혀있는 n개의 카드가 주어졌고 두개 이상의 카드는 똑같은 숫자가 적혀있을 수 있다. 이 카드들로 두개 혹은 세개를선택해 곱이 최대가 되도록 해라. 다음의 6개 카드로 예를 들겠다: 5, 10, -2, 3, 5 그리고 2. 만약 5, 10, 5를 선택한다면 결과로 250이 나올 것이고 250이 최대가 될 것이다. 4개 카드로 또 다른 예를 들겠다: 10, 0, -5, 2가 주어졌다고 하자. 10과 2 두개의 카드를 고르면 결과로 20이 나올 것이고 20이 최대가 될 것이다.n개의 카드가 주어졌을 때, 2개 혹은 3개의 카드를 선택해 최대의 결과를 출력해라. 복잡하게 생각할 것 없이 배열을 정렬..

문제 링크입니다: https://www.acmicpc.net/problem/4963 DP에서 자주 나오던 간단한 그래프 이론 문제였기 때문에 쉽게 풀 수 있는 문제였습니다. 알고리즘은 다음과 같습니다.1. 모든 그래프 좌표를 탐색하면서 아직 방문하지 않았고 섬이면 탐색을 시작합니다.2. 해당 좌표에서 갈 수 있는 모든 곳을 밟으며 방문했다고 표시를 합니다.3. 섬의 개수를 추가하고 2번 과정이 끝나면 1번을 반복합니다. #include #include //memsetusing namespace std; const int MAX = 50; int w, h;int map[MAX][MAX]; //지도bool visited[MAX][MAX]; //방문 typedef struct{ int dx, dy;}dir; ..

문제 링크입니다: https://www.acmicpc.net/problem/1065 BruteForce를 통해 각 자리수를 확인해서 한수의 개수를 구하는 문제였습니다.한수는 백의 자리 숫자부터 판별할 수 있으므로 idx>1일 때부터 판별을 진행하였습니다.주석을 자세히 작성했기 때문에 별도의 설명은 필요 없을 것 같습니다! #include using namespace std; int X; int arithmeticSequence(void) { int cnt = 0; int digit[4]; //1000보다 같거나 작으므로 for (int num = 1; num 1) { //십의 자리수와 일의 자리 수 차를 저장 int difference = digit[1] - digit[0]; //한수 판별 for(int..

문제 링크입니다: https://www.acmicpc.net/problem/1660 언제나처럼 Top-Down 방식으로 접근했지만 메모리 에러가 발생했습니다.접근 방법은 Bottom-Up 방식과 유사하게 했지만 재귀호출을 너무 많이 하여 오류가 뜨는 것 같습니다. #include #include #include //memset using namespace std; const int MAX = 300000 + 1; //cannon[121] = 302621 const int CANNONMAX = 121 + 1; int N; int cannon[CANNONMAX]; int cache[MAX]; void preCalculate(void) { //사면체 각 줄에 필요한 대포 개수 구하고 for (int i = 1..

문제 링크입니다: https://www.acmicpc.net/problem/2869 굳이 이분탐색법으로 안 풀어도 되지만 이분탐색법 분류에 들어가 있는 문제였기 때문에 BinarySearch를 이용하여 풀었습니다.달팽이는 하루에 (A-B)만큼 움직이고 마지막날에는 A만큼 올라가서 목표지점에 도달하거나 초과합니다.따라서 결과는 totalDay(mid)가 아닌 totalDay+1이여야 합니다.그리고 한가지 주의할 점은 INF를 1,000,000,000 이상으로 설정해야한다는 점입니다. (1 ≤ B < A ≤ V ≤ 1,000,000,000) #include #include using namespace std; const int INF = 1000000000 + 1; int A, B, V; long long ..

문제 링크입니다: https://www.acmicpc.net/problem/1562 계단수의 대한 개념은 http://jaimemin.tistory.com/359?category=988050(쉬운 계단수)를 통해 익혀놓았기 때문에 쉽게 접근할 수 있었던 문제였습니다.하지만 이 문제에서는 10844번과 다르게 0~9 모두 등장해야 계단수라고 여깁니다. 처음에 문제를 풀었을 때는 접근 방법은 맞았지만 메모이제이션 시 0~9가 사용되었는지 표기하는 배열을 고려안해서 틀렸습니다.아래는 제가 처음에 작성한 코드입니다. #include #include //memset using namespace std; const int MAX = 100 + 1; const int MOD = 1000000000; int N; in..

문제 링크입니다: https://www.acmicpc.net/problem/3943 왜 DP 문제로 분류된지 모르겠는 문제였습니다.정말 간단하게 재귀함수를 호출해도 AC를 받을 수 있기 때문입니다. #include using namespace std; int N, maxNum; int maxHailStone(int N) { if (maxNum > test_case; for (int i = 0; i < test_case; i++) { scanf("%d", &N); maxNum = N; printf("%d\n", maxHailStone(N)); } return 0; } 개발환경:Visual Studio 2017 지적, 조언, 질문 환영입니다! 댓글 남겨주세요~