목록c++ (497)

1일1알

백준 2617번 구슬 찾기 C++

자기보다 가벼운 것과 무거운 것 두 경우의 그래프를 만들고, 둘 중 하나라도 자기의 자식의 수가 n/2보다 크다면 중간이 될 수 없다. #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using ll = long long; int hs = 0; int ls = 0; vector light(100, vector()); vector heavy(100, vector()); vector visited1(100, false); vector visited2(100, false); void dfs1(int..
알고리즘 2022. 3. 1. 11:02
백준 2206번 벽 부수고 이동하기 C++

동일한 지점에 늦게 도착하더라도 벽을 부술 수 있는 기회가 남아있으면 벽을 부수지 못하는 먼저 도착한 경우보다 먼저 목적지까지 도달할 수 있기 때문에 방문 여부를 기록하는 배열을 벽을 부술 수 있는 상태에서 방문한 것과 부수지 못하는 상태에서 방문한 것 두 가지로 나눠서 문제를 해결하였다. #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using ll = long long; struct Info { int row; int col; int dist; int chance; }; int dRow[..
알고리즘 2022. 2. 28. 12:05
백준 1987번 알파벳 C++

백트래킹을 이용해서 해결할 수 있는 문제이다. 처음에 방문한 알파벳을 set에 저장해서 이미 방문한 곳인지 확인해서 풀었더니 시간초과가 났다. 그래서 알파벳 개수의 크기의 visited 배열을 만들어서 방문 체크를 O(1)에 할 수 있도록 수정했더니 통과되었다. #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using ll = long long; int r, c; int ans = 0; int dRow[4] = { -1,0,1,0 }; int dCol[4] = { 0,1,0,-1 }; vec..
알고리즘 2022. 2. 27. 12:36
백준 2748번 피보나치 수 2 C++

dp[ i ] = dp[ i - 2 ] + dp[ i - 1 ] , int 범위를 넘어가기 때문에 long long으로 선언하였다. #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using ll = long long; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); vector dp(91, 0); dp[1] = 1; int n; cin >> n; for (int i = 2; i
알고리즘 2022. 2. 26. 11:09
백준 4577번 소코반 C++

문제에 써있는대로 구현하였다. #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using ll = long long; int dRow[4] = { -1,0,1,0 }; int dCol[4] = { 0,1,0,-1 }; int target_cnt = 0; int goal_cnt = 0; vector board(15, vector(15)); pair Move(int row, int col, int dir) { int nextRow = row + dRow[dir]; int nextCol = col ..
알고리즘 2022. 2. 25. 13:40
백준 11066번 파일 합치기 C++

i~j의 최소비용은 i ~ m - 1 의 비용 + m ~ j 의 비용 중 제일 작은 값이다. (m은 i ~ j 사이의 값) 문제를 풀면서 여기까지는 접근했는데 합을 더해주는 부분을 생각하지 못해서 조금 헤맨 것 같다. #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using ll = long long; const int INF = 987654321; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); ve..
알고리즘 2022. 2. 23. 13:31
이전 Prev 1 ··· 65 66 67 68 69 70 71 ··· 83 Next 다음