노는 게 제일 좋아

코딩테스트에서 유용한 헤더라고 할 수 있다. #include // 문자 관련 함수들의 원형 이 헤더에 문자열에 엄청 유용한 함수들이 들어있다. int isalnum(); //알파벳이나 숫자이면 true int isalpha(); //알파벳이면 int isblank(); // 공백이나 tab이면 int iscntrl(); // 제어문자이면 int isdigit(); // 십진 숫자이면 int isgraph(); // 빈칸이 아닌 인쇄할 수 있는 문자면 int islower(); // 소문자이면 int isprint(); // 빈칸을 포함한 인쇄할 수 있는 문자면 int ispunct(); // 구두점 문자이면 int isspace(); // 빈칸이면 int isupper(); // 대문자면 int isxd..

음.. 생각은 빨리했는데.. 오래걸림.. 왜냐면.. 초기화를 잘못했다. 아...내 1시간반 https://www.acmicpc.net/problem/14502 그렇게 어렵지 않았다. 벽을 무작위로 세워야 하는 것을 이미 알기에.. Brute Force를 해야하는 것은 알았지만 그냥 백트래킹 복습삼아 적용했다. 가장 처음 제출한 풀이.. #include #include #include #define X first #define Y second using namespace std; int map[8][8]; int visited[8][8]; int dx[4] = {1,-1,0,0}; int dy[4] = {0,0,1,-1}; int N,M; int ans = 64; stack stk; // DFS 스택 ve..

우선 숫자가 큰 문제이다. 뭔가 크다. 어렵진 않았지만.. 그냥 오랜만에 푸니까 감이 안왔다. https://www.acmicpc.net/problem/2805 시간초과 될 것을 알면서도 brute force로 해봤다. #include using namespace std; int N,M; int maxi = 0; int sum; int arr[1000001]; int main(){ cin >> N >> M; for(int i = 1; i> a; arr[i] = a; if(a>=maxi){ maxi = a; } } maxi--; while(1){ sum = 0; for(int j = 1; j0) sum += temp; } if(sum>=M){ break; } maxi--; } cout > N >> M; f..

어렵지 않지만.. 헷갈렸다. 행과 열을 바꿔서 해버렸따.. https://www.acmicpc.net/problem/2225 #나의 풀이 #include #define MAX 1000000000 using namespace std; int N, K; long long dp[201][201]; // N, K int main() { int i, j, k; cin >> N >> K; //하나를 선택할 때는 무조건 하나를 선택함. for (i = 0; i

어려웠다. 부분으로 쪼갤 수 있었지만 생각이 잘 안났다. https://www.acmicpc.net/problem/9251 모든 부분을 부분수열로 쪼개보니.. for문이 3개나 나와서 그냥 떄려쳤다. DP문제라는 것을 한 번에 파악할 수 있었다. 어떻게 전체 문제를 부분으로 쪼갤 수 있을까 고민했다. 처음에는 맨앞에서부터 접근했지만 틀린 접근법이었다. 마지막부터 조사했어야 했다. 길이가 L1, L2의 문자열이 있다. 만약 마지막 부분이 같다면 해당 마지막부분을 제외한 채로 나머지 L1 -1 , L2 - 1의 문자열의 가장 긴부분을 조사하면 될 터였다. 마지막 부분이 다르다면 둘 다 제외하는 것이 아닌 L1 - 1, L2 또는 L1, L2 - 1의 문자열을 조사하면되었다. 그리고 문자열이 비어있는 것과의 ..

용량도 작다 https://www.acmicpc.net/problem/2293 심히 기분이 좋지 않다. 재귀로 푸는 방법을 알았지만.. 용량도.. 시간도 초과할 것이 뻔했다. 다른 방법을 찾는데.. 너무 헤맸다. 이러한 방법은 정말 많은데 충분히 익혀놔야할 방법 중 하나같다. 하향식보다 이번엔 상향식으로 하는 것이 맞았다.dp에 저장해가며 푸는 것이 이 문제의 핵심이었을 것이다. #include using namespace std; int n,k; int coin[101]; int dp[100001]; int main(){ cin >> n >> k; for(int i = 1; i> a; coin[i] = a; } //dp[0] = 1 을 추가시켜주어야함 //첫번째 코인으로 만들 수 있는 경우의 수를 추가..

다이나믹 프로그래밍이 재밌어지는 시기 https://www.acmicpc.net/problem/2193 우선 예를 몇개 들고나보면 하위 문제로 쪼개지는 것을 알 수 있고 하위 문제에 대해 답을 구하면 된다. 재귀함수로 구현을 해보고 해당 함수를 Memoization 하게되면 시간 안에 풀어진다. #include using namespace std; int N; long long dp[91][2]; int main(){ cin >> N; dp[1][1] = 1; dp[2][0] = 1; for(int i = 3; i

바로 생각한 대로 실행하면 되는 문제다. https://www.acmicpc.net/problem/2003 우선 N~M번째 까지의 합은 1~M - 1~N-1 인것을 나는 이용했다. 하지만 이제부터는 잘한 사람들에게서도 나와 무엇이 다른지 공부하기로 했다 우선 나의 풀이를 보고 다른 잘한 사람들의 풀이를 비교해보자 #맞은 풀이 #include using namespace std; int N,M; int arr[10001]; int dp[10001]; // dp[i] -> 1~i번째까지의 합 // N~M 까지의 합은 1~M번째 까지의 합 - 1~N-1 번째까지의 합. int main(){ cin >> N >> M; int cnt = 0; for(int i=1; i> arr[i]; dp[i] = dp[i-1]..

https://www.acmicpc.net/problem/1094 처음에 생각했을 때.. 이진법? 생각났다. 문제를 읽고 예를 읽어보니 맞다. 즉, 이진법 수에서 1의 개수를 구하는 문제다. 즉, 우리가 이진법 변환을 어떻게 했는지 생각해봤다. 2로 나누면서 나머지를 세었다. 마지막까지 2로 나누어서 숫자를 판단했다. 코딩도 그렇게 했다. #include using namespace std; int N; int main() { cin >> N; int sum = 0; while (N >= 1) { sum += N % 2; N /= 2; } cout

1초지만 은근히 숫자가 적어서 해볼만하다 생각한 문제 https://www.acmicpc.net/problem/18111 처음에 든 생각은.. 다 조사해볼 생각은 안했고.. 어떠한 것이 가장 최소 시간을 가질지 계산해보기로 했다. 당연히 모든 블럭에 대한 평균 높이로 만드는 것이 최소시간이 걸릴 것이라 생각했다. 뭐 시간이 달라서 틀린 생각이 되었고 또한 답이 같을 경우 높이가 높은 것 까지 조사해봐야 했으므로 전수조사를 해야했다. brute force란다. 처음에 틀린 풀이를 보자 #include #include using namespace std; int N, M, B; //(1 ≤ M, N ≤ 500, 0 ≤ B ≤ 6.4 × 10^7) int minh = 257; int maxh = -1; int..