광그로

문제 : https://www.acmicpc.net/problem/1799 오답 (최초코드)아래의 방식으로 풀이 시, 체스말이 서로 잡을 수 없는 위치하는 것은 맞다.하지만, 체스말이 최대의 개수로 존재하는 것은 아니다.#include #include using namespace std; int n; int map[10][10]; int res[10][10] = { 0 }; bool func_check(int y, int x) { for (int i = y, j = x; i >= 0; i--, j--) { // 북서 if (res[i][j] != 0) return false; } for (int i = y, j = x; i >= 0; i--, j++) { // 북동 if (res[i][j] != 0) r..

LIS(Longest Increasing Subsequence) 최장 증가 부분 수열 LIS의 기본적인 예를 들어보이자면, 8 2 9 1 4 11 6 7 5 10 의 수열이 주어졌을 때, 8 2 9 1 4 11 6 7 5 10 혹은8 2 9 1 4 11 6 7 5 10 를 나타내는 것이다. 1. 앞에서 부터, 순차적으로 수를 선택하여 나갈 때,2. 수는 증가하여야 하며,3. 그 선택되어진 숫자가 가장 많은 경우를 찾는 것이다. void LIS() { lis[0] = 1; for (int i = 1; i lis[i]) { lis[i] = lis[j] + 1; } } } } 위의 그림과 같은 순서로 lis배열에 값이 채워지게 된다.최종적으로 최장 증가 부분 수열을 찾기 위해선, lis배열의 값들 중 가장 큰..

문제 : https://www.acmicpc.net/problem/2579 #include #include using namespace std; int n; int arr[100001]; int dp[500005][3]; void func() { dp[1][0] = 0; dp[1][1] = arr[1]; dp[1][2] = 0; dp[2][0] = arr[1]; dp[2][1] = arr[2]; dp[2][2] = dp[1][1] + arr[2]; for (int i = 3; i > n; for (int i = 1; i > arr[i]; } func(); cout

문제 : https://www.acmicpc.net/problem/2578 25개의 칸을 5X5 이중배열로 생각하였다가, 시간이 너무 오래 걸릴 것 같아 1차원배열의 연장으로 생각하였다.#include #include using namespace std; int map[25]; int cnt=0; int search(int n) { for (int i = 0; i 0..

문제 : https://www.acmicpc.net/problem/2591 DP로 생각하지않고 짜본 소스코드n을 int나 long long 으로 호출하는 방법으로 하였을 시, 테스트 케이스들이 잘 출력되는 것처럼 보였다.하지만, int형은 약 9자리의 정수를, long long형은 약 15자리의 정수를 갖을 수 있어, 그 이상 초과되는 자리들은 결과값이 0이 출력되었다.이 점을 보완하고자, n을 문자열로 입력받아 정수로 변환하는 과정을 거쳐보았지만, 시간초과가 뜬다. 오답#include #include #include #include #include using namespace std; //long long n; char n[41]; int t = 0; int arr[41] = { 0 }; int arr..

문제 : https://www.acmicpc.net/problem/2590 힌트1. 길이 6칸의 색종이는 +1개의 판이 필요하다.힌트2. 길이 5칸의 색종이는 +1개의 판이 필요하다. 또한, 길이 1칸이 11개의 공간이 생긴다.힌트3. 길이 4칸의 색종이는 +1개의 판이 필요하다. 또한, 길이 2칸이 5개의 공간이 생긴다.힌트4. 길이 3칸의 색종이는 +1개의 판이 필요하다. 또한, 길이 2칸은 (길이 3칸 빈 공간 개수)*2 - 1개가 생기고, 길이 1칸은 (길이 3칸 빈 공간 개수)+4개가 생긴다.힌트5. 길이 3칸의 색종이는 길이 2칸의 색종이 1개, 길이 1칸의 색종이 5개로 구성되어있다.힌트6. 길이 2칸의 색종이는 길이 1칸의 색종이 4개로 구성되어있다. #include #include #in..

문제 : https://www.acmicpc.net/problem/2608 문자열에서 자연수로 변경하는 과정에서는 현 위치에 있는 문자와 다음 위치에 있는 문자가 가지고 있는 크기를 비교하여 결과값을 내어준다. 자연수에서 문자열로 변경하는 과정에서는 조건1. 자연수의 자릿수 10^3, 10^2, 10^1, 10^0조건2. 각 자릿수에서 9, 8~5, 4, 3~0이 등장를 고려해 주어야한다. #include #include #include #include #include using namespace std; int main() { char s[15]; int alphabet[91]; //A~Z : 65~90 alphabet['I'] = 1; alphabet['V'] = 5; alphabet['X'] = 1..