노는 게 제일 좋아

항상 N번째 일때는 어떻게 해야 가장 길어질까? 이전의 어느 원소를 가져와야할까?? 생각을 해보자 https://www.acmicpc.net/problem/11053 #맞는 풀이 #include #include using namespace std; const int MAX = 1001; int N; int arr[MAX]; int dp[MAX]; int main(){ cin >> N; int ans = 0; for(int i = 1; i> x; arr[i] = x; } //초기값 fill(dp, dp+1001, 1); //자기자신은 항상 포함되므로 최소 1 for(int i = 1; i

이 문제도 DP다. 과연 N번째 동전은 어느 것을 가져와야할까?를 생각해보자 N-1번째 동전은 무엇을 쓰는 것이 좋을까 생각해보자 https://www.acmicpc.net/problem/2294 #맞는 풀이 #include #include #include using namespace std; const int MAX = 10001; int N,K; int dp[MAX]; vector vec; int main(){ cin >> N >> K; fill(dp, dp+10001, MAX); //우선 min에 걸리지 않게 충분히 크게 MAX로 초기화 for(int i = 0; i> x; vec.push_back(x); if(x>10000)continue; //어차피 K보다 가치가 큰 동전은 쓰지 않음 dp[x]..

감이 안잡히면 가장 어려운게 DP가 아닐까.. 이것도 그렇다. https://www.acmicpc.net/problem/1915 #맞는 풀이 #include #include #include #include using namespace std; int n, m; int map[1001][1001]; int main() { cin >> n >> m; //최솟값 int ans = 0; for (int i = 0; i > s; for (int j = 0; j < m; j++) { map[i][j] = s[j] - '0'; //만약 1이 등장하면 최소 ans = 1 if (map[i][j] == 1) ans = 1; } } //1,1부터 시작하므로 나머지에 대한 계..

물론 처음부터 생각은 안나겠지만 가장 DP다운 문제가 아닌가 싶다. 항상 N번째 항을 어떻게 구해야할까 생각하면 DP의 답은 나오지만.. 항상 생각나는 것은 아니다. https://www.acmicpc.net/problem/11055 #맞는 풀이 #include #include using namespace std; int N; int arr[1001]; int dp[1001]; int main(){ cin >> N; int ans = 0; for(int i = 1; i> arr[i]; } //dp[i] -> arr[i]를 증가 부분 수열의 마지막이라 할 때의 부분 수열의 합. //즉, 현재 위치의 값을 더한 것이 dp[i]에 저장됨 //dp[i]채우기 for(int i = 1; i

처음부터 생각하기는 힘들다. DP라는 것을 예상할 수 있지만 점화식을 바로 생각하기는 어렵다. https://www.acmicpc.net/problem/1699 #맞는 풀이 #include #include using namespace std; // 100000을 루트하면 대충 350 이하.. //또한 최소항의 수를 만들기 위해 큰 것부터 집어넣기로함, 그리드 // 그리드로 안풀림..ㅎ dp로 풀어야할 듯. int arr[100001]; int N; int main(){ cin >> N; //모든 N에 대해서 최소항의 개수를 찾아봄 for(int i = 1; i 어떤 제곱수 항을 가져야 최소 개수를 가질지 다 뒤져봄 // -> 그리디는 틀린 방식 18 = 4^2,1^2,1^2 지만 사실 3^2,3^2가 더..

이것도 정말 구현문제로써 시키는대로 하면 된다. 다만 어떻게 구현할까? 의 선택지에서 DFS를 골랐다면 고생을 덜 할 것이었다 https://www.acmicpc.net/problem/14500 #맞는 풀이 #include #include #include using namespace std; int dx[4] = {1,-1,0,0}; int dy[4] = {0,0,1,-1}; int N,M; int map[500][500]; bool visited[500][500]; // 멍청했따.. 어차피 4칸을 사용하는 건데... DFS로 풀었으면 되었다는 힌트를 듣고.. 현타온다. //즉 DFS로 4칸 탐색하는 과정에 일자 모양도 있고 네모도있고 기역자도 있다. //다만 ㅗ 모양만 DFS로 탐색은 불가능하다. in..

이것도 정말 구현문제로써 시키는대로 하면 된다. 다만 범위에 신경쓰도록 사용자 입력만이 범위가 아니란 것을 명심하자 https://www.acmicpc.net/problem/21608 #맞는 풀이 #include #include #include #define X first #define Y second using namespace std; int seat[21][21];//자리 배치 1~N만 쓸 것임 int dx[4] = { 1,-1,0,0 }; //방향 int dy[4] = { 0,0,1,-1 }; //방향 int good[5] = { 0,1,10,100,1000 }; //점수 int N; vector info[401]; //학생 번호와 선호하는 학생을 저장 int main() { cin >> N; i..

문제대로 구현하면 된다. 하지만 어렵지는 않았다. 그냥.. 중간에 if 조건문에서 == 써야할 것을 =으로 써서 30분 날렸다. https://www.acmicpc.net/problem/3190 # 맞는 풀이 #include #include #include #define X first #define Y second using namespace std; //하 상 우 좌 -> 좌측 위 기준 int dx[4] = { 1,-1,0,0 }; int dy[4] = { 0,0,1,-1 }; int N, K, L; int map[100][100]; char direction[10001]; queue q; //꼬리 잘라내기 //1.머리를 hx,hy로 옮김, 게임시간 cnt int Move(int hx, int hy, ..

어렵다. 다익스트라를 배웠지만 코딩테스트에서 다시 쓰니까 어렵다 https://www.acmicpc.net/problem/1753 #맞은 풀이 #include #include #include #include #include #define INF INT_MAX using namespace std; int V,E,start; //벡터를 원소로 가지는 배열 -> vector adj[20001]; // 인접행렬 from,(weight,to) //-> adj[1] = {3,5} 의 의미 1번 정점에서 5번으로 가는 가중치 3 //이런 그래프에서 최단거리 => 다익스트라 테이블 int table[20001]; //최소 간선을 위한 minHeap {거리, 정점 번호} -> 일반적으로 first를 기준으로 오름차순으로..

어렵지 않았다 다만 첫번째로 못풀었다. 왜 그런지 고찰해보자 https://www.acmicpc.net/problem/1543 #맞은 풀이 #include #include using namespace std; int main() { string s; string target; getline(cin, s); getline(cin, target); int size = target.size(); int cnt = 0; while (1) { int idx = s.find(target); //찾았으면 해당 문자열에서 삭제 if (idx != string::npos) { auto it = s.begin() + idx; //s.erase(it, it+size); -> 삭제 s = s.substr(idx + size)..