꾸준함

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

문제 링크입니다: https://www.acmicpc.net/problem/9252백준 9251번인 LCS(http://jaimemin.tistory.com/370?category=988050)를 풀었다면 쉽게 풀 수 있는 문제였습니다.인덱스를 하나씩 증가하며 공통부분을 찾아내는 식으로 프로그램을 작성했습니다. /* LCS(Longest Common Subsequence, 최장 공통 부분 순열) 문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. LCS의 길이와 공통부분을 구하시오 */ #include #include #include #include //memset using namespace std; int cache[1000][1000]; //최대 길이 1..

문제 링크입니다: https://algospot.com/judge/problem/read/PROMISESTICTACTOE(http://jaimemin.tistory.com/377?category=985009)와 비슷하게 보드의 모든 경우의 수를 미리 계산하고 푸는 문제였습니다.인상적이였던 점은 보드를 5*5 이차원 배열로 표현하지 않고 비트 시프트 연산을 이용하여 25자리로 만들어 표현했다는 점이였습니다.비록 보드가 비어있을 경우 160만가지의 경우의 수를 세야하기 때문에 속도는 조금 느리다해도 상당히 효율적인 코드인 것 같습니다. #include #include #include #include //memset using namespace std; char cache[1 50) exit(-1); preC..

문제 링크입니다: https://www.acmicpc.net/problem/9461상당히 쉬운 문제였습니다.규칙이 명확하기 때문에 적절히 재귀를 이용해주면 됩니다. /* 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 길이를 k라 했을 때, 그 변에 길이가 k인 정삼각형을 추가한다. 파도반 수열 P(N)은 나선에 있는 정삼각형의 변의 길이이다. P(1)부터 P(10)까지 첫 10개 숫자는 1, 1, 1, 2, 2, 3, 4, 5, 7, 9이다. N이 주어졌을 때, P(N)을 구하는 프로그램을 작성하시오. */ #include #include //memset using namespace std; int N; long long..

요리 왕국에서 발견한 보물 사진 파워문을 얻는 방법을 공유하고자 합니다.우선 요리 왕국 보관소로 워프를 합니다. 워프를 하면 후라이팬을 던지는 거북이(이름을 까먹었습니다)가 있을텐데캐피를 던져 캡쳐를 합니다. 캡쳐한 후에는 높은 점프력을 갖추게 되기 때문에 쉽게 이 곳으로 올라올 수 있습니다. 치즈에서 한칸 더 올라간다면 보물 사진을 확인할 수 있습니다.정확한 위치는 지도를 통해 보여드리겠습니다. 맞게 이동했다면 지도에 해당위치가 표시될 것입니다. 나중을 위해 보물의 힌트 스크린샷을 찍는 것을 권장합니다. 보물의 힌트를 확인한 뒤에는 바다 왕국으로 이동합니다. 바다왕국에 도착하면 커다란 해구 서쪽에 워프를 합니다. 워프를 하자마자 앞에 있는 물고기에 캐피를 던져 캡쳐를 합니다. 사실 바로 앞에 있는 위치..

바다 왕국에서 발견한 보물 사진 파워문을 얻는 방법을 공유하고자 합니다.바다 왕국에서 해당 위치로 이동을 합니다.오디세이호에서 절벽을 따라 올라가면 해당 위치에 쉽게 갈 수 있습니다. 잘 도착했다면 위와 같이 보물 힌트 그림을 확인할 수 있습니다. KEEP이라고 써 있는 것을 확인할 수 있습니다! 보물 힌트를 스크린샷하고 도시 왕국으로 이동합니다. 그 다음 메인 스트리트 입구로 워프를 합니다. 줄넘기 달인을 클리어 할 때 큰 도움이 된 오토바이가 있는 위치로 이동하면보물 힌트에서 봤던 KEEP을 도로 위에서 볼 수 있습니다.그림처럼 E와 E 사이에 서서 B+ZL을 눌러 엉덩방아를 찍으면 파워문을 얻을 수 있습니다! 이상 바다 왕국에서 발견한 보물 사진 파워문을 얻는 과정이었습니다! *파워문에 관한 질문을..

문제 링크입니다: https://algospot.com/judge/problem/read/NUMBERGAME틱택토 문제(http://jaimemin.tistory.com/377?category=985009)와 구조적으로 유사한 문제입니다.재귀함수가 얼마나 강력한지 확인할 수 있었던 문제였습니다. /* n개의 정수를 일렬로 늘어놓은 게임판을 가지고 현우와 서하가 게임을 한다. 게임은 현우부터 시작해서 번갈아가며 진행하며, 각 참가자는 자기 차례마다 두 가지 일 중 하나를 할 수 있다. 1.게임판의 왼쪽 끝에 있는 숫자나 오른쪽 끝에 있는 숫자 중 하나를 택해 가져간다. 가져간 숫자는 게임판에서 지워진다. 2.게임판에 두 개 이상의 숫자가 있을 경우, 왼쪽 끝에서 2개, 혹은 오른쪽 끝에서 2개를 지운다.(..

문제 링크입니다: https://algospot.com/judge/problem/read/TICTACTOE보드 위에 표시될 수 있는 모든 경우의 수(3^9)를 계산한다는 점이 흥미로운 문제였습니다.3*3 보드 위에서 진행되는 게임인데도 경우의 수가 3^9이나 되는데 바둑판의 경우의 수를 계산하는 알파고가 얼마나 대단한지 새삼 깨닫게 되었습니다. /*틱택토는 3x3 크기의 게임판에서 하는 3목 게임이다. 두 명이 번갈아가며 o와 x를 게임판의 빈 칸에 쓰되, 먼저 같은 글자를 가로, 세로 혹은 대각선으로 3개 쓰이도록 하는 쪽이 이긴다.틱택토 게임판의 현재 상태가 주어진다. 두 사람 모두 최선을 다한다고 가정할 때, 어느쪽이 이길지 판단하는 프로그램을 작성하시오.*/#include #include #inc..