노는 게 제일 좋아

어렵지 않지만.. 헷갈렸다. 행과 열을 바꿔서 해버렸따.. 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/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

DFS, BFS 알고리즘을 알아야 풀 수 있는 문제다. https://www.acmicpc.net/problem/17298 이것은 그냥 뭐 생각대로 하기 쉽지 않다. 해보려 했는데..인덱스가 저장이 안되어서 정말 힘들었다.그래서 pair를 쓸까 하다가.그냥 스택 2개를 썼다. 인덱스를 이용해야 한다라는 생각을 하면 어렵지만 생각할 수 있는 문제라고 한다.한 번에 생각하기는 확실히 힘든 것 같다. 다른 사람과 풀이를 비교하지 않는 이유는원리는 같아서 그렇다. #include #include #include #include using namespace std; stack num; // 숫자를 넣음 stack stk; // 인덱스를 넣음 int N; int arr[1000001]; void init(){ io..

DFS, BFS 알고리즘을 알아야 풀 수 있는 문제다. https://www.acmicpc.net/problem/1260 이것은 그냥 뭐..그냥 구현하면 된다. 다만 여기서 주의할 점은 방문을 언제할 것이냐를 판단하느냐 문제다. 나머진 어렵지 않다. 그냥 머릿속에서 생각하는 그대로 구현한다. #include #include #include using namespace std; int N, M, V; // 정점, 간선, 시작 노드 int map[1001][1001]; int visited[1001]; int backup[1001]; queue Q; stack S; void copy(int origin[1001], int backup[1001]) { for (int i = 1; i > N >> M >> V;..

바로 생각한 대로 실행하면 되는 문제다. 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]..

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..

백트래킹의 전형적인 문제 조건을 잘 읽어야 하는 문제 https://www.acmicpc.net/problem/15654 #맞은 풀이 #include #include #include using namespace std; int N, M; vector vec; vector ans; bool check[8]; void func(int cnt) { if (cnt == M) { for (auto v : ans) { cout > M; for (int i = 0; i > a; vec.push_back(a); } sort(vec.begin(), vec.end()); // 오름차순정렬 func(0); } 다 비슷한 문제다. 이러한 N이 다 다른 숫자가 주어져서 그렇지 만약 중..

왜 DP 알고리즘 분류에 들어있는지 모를 문제 https://www.acmicpc.net/problem/4963 테스트 케이스가 많은 문제는 어차피 하나에 대해서 풀 수 있다면 모조리 풀 수 있고 ios::sync_with_stdio(0); cin.tie(0); 을 꼭 써주자. 이건 그냥 따로 공부할 필요도 없다. 그냥 대각선까지 가능한 BFS를 풀면된다. 탐색을 4방향에서 8방향으로 늘리면 되는 문제다. 다를게 하나도 없다. #맞은 풀이 #include #include #include #define X first #define Y second //8방향으로 이동가능 제자리 빼고 int dx[8] = {1,1,1,0,0,-1,-1,-1}; int dy[8] = {-1,0,1,-1,1,-1,0,1}; us..

전형적인 DP문제다. 처음엔 백트래킹으로 풀려했으나.. 개수가..너무 많아서 백트래킹을 어떻게 캐시로 저장할까하다가.. 방향을 틀었다. https://www.acmicpc.net/problem/11052 #처음 틀린풀이 #include using namespace std; int N; int card[1001]; int dp[1005][1005]; //카드를 살 때, 카드 수는 적되 가격은 높게 사야한다. //현재 카드가 i개 가지고 있고 카드의 수와 가격을 보면서 골라야 한다. //결국 다 뒤져봐야함 int M = -1; //최댓값 int x = 0; int func(int cnt, int val){ if(dp[cnt][x] > 0) return dp[cnt][x]; //종료조건 if(cnt > N)r..