east-wind 님의 블로그

#include #include using namespace std;long long dp[101][101];int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int N, M; long long K; cin >> N >> M >> K; // dp 테이블 초기화 for (int i = 0; i 1000000000) dp[i][j] = 1000000001; // cap 처리 } } } // K번째 문자열이 존재하지 않는 경우 if (dp[N][M] 0 || M > 0) { if (N == 0) { // 남은 건 z 뿐 ..

백트래킹 문제 오랜만에 풀어서 그런가 감을 잃은 것 같다. 분명 맞게 풀었는데 틀려서 지피티한테 물어보니 visited를 다시 false로 바꿔주지 않았다... 그리고 아무 생각없이 dp없는 백트래킹으로 해서 시간초과도 났다. 리마인드 했으니 됐다.#include #include #include using namespace std;//4^250이니까 일반 dfs로는 당연히 안됨.. dp로 줄이기//백트래킹시 visited 다시 false로 바꿔주는거 생각int N, M;int board[51][51];int dp[51][51];bool visited[51][51];string s;bool move_infinite = false;int dx[4] = {1, -1, 0, 0};int dy[4] = {0, 0..

25분 걸렸다. 이게 왜 레벨 3이지..?? 항상 느끼지만 프로그래머스의 레벨 선정 기준은 참 모르겠다. 좀 쉽게 푼 dp 문제였다.#include #include#include using namespace std;//1 tops) { int answer = 0; dp[0][0] = 1; dp[0][1] = 1; dp[0][3] = 1; if(tops[0]) dp[0][2] = 1; else dp[0][2] = 0; for(int i = 1; i

다익스트라는 음수인 싸이클이 있으면 안된다!!!처음에 다익스트라로 접근하다 아닌거 같아 dfs로 접근했는데 시간초과가 났다. 사실 당연한거긴한데.. dp도 생각은 해보았으나 순서때문에 안될 거 같았다. 결국 알고리즘 힌트를 봤는데 dp였다 ㅋㅋdp로 좌측에서 우로 한번, 우측에서 좌로 한번 흝는 식으로 했는데 접근은 맞으나 한줄 한줄마다 이렇게 했어야 했다. 나는 위->아래/좌->우 이중 for 하나, 위->아래/우->좌 이중 for 하나 이런식으로 해서 꼬였던 것 같다. 골드 상위티어 문제 가니 거의 생으로는 못푸는 수준인게 참 슬프다.#include #include#include#include#include#include #includeusing namespace std;//한번 탐색한 곳 탐색 x,..

빨리 풀었다. 예전에 풀었던 동전 문제하고 똑같았다.#include #include#include #includeusing namespace std;int T,n;//1> T; for(int k = 0; k > n; memset(dp,0,sizeof(dp)); for(int i = 1; i

20분 걸렸다. dp로 풀었는데 사람들은 다익스트라로 많이 푼 듯 했다. 생각해보면 K라는 목적지로 N에서 가는 것이니 다익스트라를 쓰는게 생각하기에 나을 수도 있겠다. 그래서 풀고 나서 다익스트라로도 풀어봤다.1. dp#include #include #include #include#include#include#includeusing namespace std;//20분걸림int N,K;//N,K> N >> K; for(int i = 0; i 2. 다익스트라조건분기의 순서를 잘못 써서 배열 인덱스 초과 에러가 났다.#include #include #include using namespace std;int N, K;vector time(200001, 1e9); // 각 위치까지 걸리는 최소 시간 저장s..

30분정도 걸렸다. 푼문제라서 기억이 날 줄 알았는데 1도 기억안났다. 처음에 완전탐색으로 풀려니 시간 초과가 났다. 시간복잡도 계산하는게 귀찮아서 빼먹었더니.. dp[i][j] = j개를 사용해서 만든 가치 i의 경우의 수로 두었고, 200^3 = 8백만 정도였기에 가능하다고 보였다. #include #include #include #include#include#include#define MAX_NUM 1000000000;using namespace std;//26분 시작long long dp[201][201];//가치 i일때 j개 사용해서 만듦int n,k,cnt=0;int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0..

예전에 풀었던 문제라 빠르게 풀었다.#include #include #include #include#include#includeusing namespace std;//8분 시작int n,k;//n> n >> k; for(int i = 0; i > coins[i]; } sort(coins, coins+n); dp[0] = 1; for(int i = 0; i

옛날에 풀었던 문젠데 중복 처리가 생각이 안났다. 그냥 반복문에서 중복 처리할 때처럼 작은 것부터 처리하면 된다.(i=1부터, j=i부터 느낌)#include #include using namespace std;int n, k, coin[101], dp[10001];int main(){ dp[0] = 1 ; cin >> n >> k; for (int i = 1 ; i > coin[i] ; for (int i = 1 ; i

M이 백만까지 가능해서 전처리를 하고 들어가야겠다는 생각을 했다. 완전탐색으로 start,end를 지정하고 탐색하면 2000^3이라 안되겠다는 생각이 들었고, dp를 이용해서 dp[i][j]가 end가 i이고, j가 start일 때 팰린드롬 여부를 저장하는 배열로 했다. dp[i-1][j+1](길이가 양쪽에서 하나씩 줄은 이전 dp값)이 1이고 양 끝값이 같으면 true인 형식으로 하였다. 로직은 금방 생각했는데 코드로 구현하는데 오래걸렸다. #include #include#include #include #include #include using namespace std;int N,M,S,E;//N> N; for(int i = 1; i > arr[i]; for(int i = 1; i = 1; ..