개인공부용123 프로그래밍 블로그

문제 : https://algospot.com/judge/problem/read/NUMBERGAME 두 사람이 서로 번갈아가면서 왼쪽 오른쪽 둘중에서 한 카드를 고르거나 게임판에 두개이상의 숫자가 있을경우 왼쪽 오른쪽 둘중에서 2개의 카드를 지우면서 게임을하는데 서로 최선을 다했을경우 나오는 결과를 출력하는 게임입니다. 가지고있는 카드중 맨 왼쪽을 begin 맨 오른쪽을 end로하고 dp를 begin과 end로 찾을수있게 배열을 이차원배열로 생성해습니다. #include #include #include using namespace std; #define IMPOSSIBLE -99999 int arr[50]; int cache[50][50]; int n; int NumberGame(int begin, in..

문제 : https://algospot.com/judge/problem/read/TICTACTOE 두명이 번갈아가면서 흑돌 백돌 대신 o와 x를 이용해서 오목이아닌 삼목을 하는데 판이 주어지고 두명이 최선을 다해서 플레이할때 누가 이기거나 비기는지 찾는 문제이다. 해당문제를 dp 없이 완전탐색으로 풀려 할 경우 많은 시간이 걸리므로 dp를 사용하기위해 해당문제를 모델링해야합니다. board 판에 나올수있는 문자는 '.' , 'x' , 'o' 셋중 하나이므로 board판이 생길수 있는 경우의수는 3^9개이므로 19683(3^9)개의 int 배열을 이용해서 dp를 이용할수있습니다. #include #include using namespace std; char board[3][3]; char init_turn..

문제 : https://algospot.com/judge/problem/read/DRAGON DP를 이용해서 드래곤 커브의 부분 문자열을 출력하는 문제입니다. 문제에서 드래곤 커브의 세대는 최대 50이므로 크기 50의 int 배열을 이용해서 DP로 구현했습니다. 부분문자의 시작부터 하나씩 문자를 출력해나가는 함수입니다. X나 Y를 N번 중첩한 길이를 length배열에 미리 저장해두고 불필요한 재귀를 줄여서 문제를 해결하면 됩니다.그리고 문자열의 시작위치는 1000000000을 넘을수 없으므로 만약 중첩길이가 1000000000을 넘으면 1000000000으로 설정하면 overflow를 예방할 수 있습니다. #include #include #include using namespace std; const i..