꾸준함

문제 링크입니다: https://www.acmicpc.net/problem/2178 전형적인 BFS 문제였기 때문에 큐를 이용하여 쉽게 풀 수 있는 문제였습니다.중요한 부분은 해당 칸과 이동하는 칸을 모두 방문 표시 처리해야한 다는 점입니다. #include #include #include #include //memset using namespace std; const int MAX = 100; int N, M; int maze[MAX][MAX]; bool visited[MAX][MAX]; typedef struct { int y, x, pathLength; //좌표와 현재까지의 길이 }dir; int minStep(int y, int x, int pathLength) { queue q; int resu..

문제 링크입니다: https://www.acmicpc.net/problem/11509 처음에 Brute Force 방식으로 풀었기 때문에 TLE가 발생했습니다. 사실 O(N^2)이기 때문에 시간 안에 풀 수 있을 줄 알았지만 문제에서 요구하는 시간 복잡도는 O(N)이였습니다.이 문제의 핵심은 더 높은 곳에서 날아오는 화살의 존재 여부를 판단하는 것이였습니다. #include #include //memset using namespace std; const int MAX = 1000000 + 1; int N; int arrowHeight[MAX]; //화살 높이 /* int balloonHeight[MAX]; //풍선 높이 bool popped[MAX]; //풍선이 터졌는지 여부 int minArrow(vo..

문제 링크입니다: https://www.acmicpc.net/problem/1500 고등학교 수학을 배웠다면 상식적으로 곱하는 숫자들끼리의 차가 적을수록 곱이 커지는 것을 알고 있습니다.따라서 아래와 같이 코드를 작성했습니다. #include using namespace std; long long S, K; //곱하는 숫자들의 차가 적을수록 결과가 커진다 long long maxMultiple(void) { long long result = 1; long long multiplier = S / K; long long cnt = S - (multiplier * K); //multiplier+1을 곱하는 횟수 //multiplier 곱하는 횟수 = K - cnt for (int i = 0; i < K - c..

문제 링크입니다: https://www.acmicpc.net/problem/1541 간단한 수학문제였습니다. 뺄셈 이후마다 괄호를 치면 최소가 됩니다. #include #include using namespace std; string str; int minResult(void){ int result = 0; string temp = ""; bool minus = false; for (int i = 0; i > str; cout

문제 링크입니다: https://www.acmicpc.net/problem/2421 우선, 에라토스테네스의 체를 이용하여 미리 1,000,000까지의 소수를 계산한 다음에 다이나믹 프로그래밍을 통해 푸는 문제였습니다.왼쪽 저금통 혹은 오른쪽 저금통에만 동전을 넣으면 되기 때문에 알고리즘은 꽤나 간단했는데 자릿수라는 변수가 있어서 조금 헤맸던 문제였습니다. #include #include #include //memset#include using namespace std; const int MAX = 1000000; int N; int cache[1000][1000]; //왼쪽 저금통, 오른쪽 저금통 //minFactor[i] = i의 가장 작은 소인수(i가 소수인 경우 자기 자신)int minFactor[..

문제 링크입니다: https://www.acmicpc.net/problem/2780 http://jaimemin.tistory.com/359과 유사한 문제였기 때문에 나름 쉽게 풀 수 있었던 문제였습니다. 다만, 비밀번호의 길이가 늘어나면서 방법의 수가 엄청 늘어나기 때문에 메모이제이션할 때 또한 MOD의 나머지를 더해줘야 AC 처리가 됩니다.알고리즘은 맞았지만 MOD의 나머지를 더해주지 않아 여러번 틀렸습니다 ㅠㅠ #include #include //memset using namespace std; const int MOD = 1234567; int cache[10][1001]; //시작 숫자, 비밀번호 길이 //기계의 번호에서 인접한 숫자 표시 int boundary[10][10] = { {0, 0,..

문제 링크입니다: https://www.acmicpc.net/problem/15701 처음 시도는 배열을 이용해서 소인수분해를 한 후 (지수+1)끼리 곱해서 약수의 갯수를 구하려고 했으나 배열을 1,000,000,000 크기로 지정할 수 없기 때문에 실패했습니다.이후에는 벡터를 이용해서 이중 for문을 돌려 algorithm 헤더에 있는 count 함수를 사용해서 찾아보려고 했지만 메모리 초과가 떴고 메모리 초과가 안 떴다고 하더라도 TLE가 떴을 것입니다.따라서 http://jaimemin.tistory.com/445의 에라토스테네스의 체에서 처럼 제곱근까지 약수의 갯수를 구한 다음에 두배를 시켜 구했습니다. 약수의 순서쌍은 대칭이기 때문에 위와 같은 방법으로 풀 수 있었습니다. #include #in..

드디어 중간고사가 끝났습니다. 사실 중간고사 공부를 하면서 꾸준히 코딩도 했어야했지만 제 역량이 부족해서.. ㅠㅠ 아무튼 문제 링크입니다: https://www.acmicpc.net/problem/1402 처음 문제를 풀 때는 모든 경우의 수를 다 구해보는 어리석은 판단을 했습니다. 당연히 TLE가 떴고 곰곰히 생각한 결과 모든 A는 A''를 만들 수 있다는 것을 깨달았습니다. 왜냐하면 A=A*1*1*1*1*1*...*1 이런식으로 필요한만큼 1을 곱할 수 있기 때문입니다. #include using namespace std; //결국 A=A*1*1*1*1*1*....*1*1 이런식으로 만들 수 있기 때문에 //모든 A는 A''를 만들 수 있다. int main(void) { int test_case; ..

문제 링크입니다: https://www.acmicpc.net/problem/5913준규와 해빈이 둘 다 고려해야한다고 생각들 수 있는 문제이지만 사실 준규가 해빈이의 시작점까지 갈 수 있는 방법의 수를 구하는 문제였습니다.즉, (0, 0)에서 (4, 4)까지 가는 방법의 수가 정답이였습니다! #include #include //memset using namespace std; int K; int result = 0, noBarrier; int farm[5][5]; typedef struct { int y, x; }Direction; Direction dir[4] = { { 1, 0 },{ -1, 0 },{ 0, 1 },{ 0, -1 } }; //N S E W void howManyWays(int y, i..

문제 링크입니다: https://www.acmicpc.net/problem/13701 http://donggod.tistory.com/54을 참고하였습니다.메모리 제한이 다른 문제들과는 달리 고작 8MB이기 때문에 배열, 벡터, 링크드리스트와 같은 자료구조는 모두 사용할 수 없는 문제였습니다.따라서 비트를 사용해야 했는데 int는 32비트이므로 비트를 최대 32개 사용할 수 있고 8MB(2^3 * 2^20)는 2^23이기 때문에 비트마스크를 이용해야지만 풀 수 있는 문제였습니다. #include //#include //using namespace std; //c++는 헤더파일이 무거우므로 실행시간 면에서 불리 //cout, cin으로 코드 작성할 경우 시간초과 int arr[(1