목록c++ (497)

1일1알

백준 2174번 로봇 시뮬레이션 C++

x,y좌표를 2차원 배열의 row, col 좌표로 변환한 뒤 시뮬레이션으로 문제를 해결하였다. #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 }; struct Robot { int num; int row; int col; int dir; }; struct Order { int num; char _order; int cnt; }; pair Convert(int ..
알고리즘 2022. 3. 20. 12:33
백준 2688번 줄어들지 않아 C++

다이나믹 프로그래밍으로 문제를 해결하였다. dp[i][j] 의 2차원 dp배열을 만들고 이 배열의 의미는 i자리 수의 마지막 숫자가 j일 때 줄어들지 않는 수의 개수이다. i자리 수의 마지막 숫자가 j일 때 줄어들지 않는 수의 개수는 i-1자리 수의 마지막 숫자가 0~j일 때 줄어들지 않는 수들의 합이다. 즉, dp[i][j] = dp[i-1][0] + .... + dp[i-1][j] 이다. #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using ll = long long; using ul..
알고리즘 2022. 3. 19. 10:43
백준 12904번 A와 B C++

처음에는 S에서 백트래킹을 해서 T로 가는 방법을 생각해봤는데 범위를 보니 무조건 시간초과가 날 것 같아서 다른 방법을 생각해 보았다. T에서 S로 거꾸로 거슬러 올라가는 방법으로 문제를 해결하였다. T의 맨 뒤가 A라면 그냥 A를 빼고 T의 맨 뒤가 B라면 B를 빼고 문자열을 뒤집어준다. 이걸 반복하다가 S와 길이가 같아졌을 때 S와 T가 일치하면 S로 T를 만들 수 있는 것이고, 일치하지 않는다면 만들 수 없는 것이다. #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using ll = l..
알고리즘 2022. 3. 18. 11:19
백준 6593번 상범 빌딩 C++

bfs인데, 상하 도 있기 때문에 보통의 2차원 배열이 아닌 3차원 배열을 이용해서 문제를 해결하였다. #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using ll = long long; int dHeight[6] ={ 1,-1, 0, 0, 0, 0 }; int dRow[6] ={ 0, 0,-1, 0, 1, 0 }; int dCol[6] ={ 0, 0, 0, 1, 0,-1 }; struct Info { int h; int r; int c; int cnt; }; int main() { ios..
알고리즘 2022. 3. 16. 12:19
백준 9084번 동전 C++

dp로 해결할 수 있는 문제이다. 배낭 채우기 문제와 비슷하다. dp[n+1][m+1]배열을 만들었다. dp[i][j]의 의미는 i번 동전까지 사용해서 j원을 만들 수 있는 경우의 수 라고 정하였다. 동전 몇개로든 0원은 언제나 만들 수 있어서 dp[i][0]은 모두 1로 초기화 해주었다. i번째 동전까지 사용해서 j원을 만들 수 있는 경우는 1) i-1번째 동전까지 사용하고 j원을 만든 상태에서 아무 행동도 하지 않는 경우와 2) i번째 동전까지 사용했는데 j-coins[i]원을 만든 상태에서 coins[i]를 추가해서 j원을 만드는 경우가 있다. 따라서 점화식은 dp[i][j] = dp[i-1][j] + dp[i][j-coins[i]] 로 세우고 문제를 해결하였다. #include #include #..
알고리즘 2022. 3. 15. 11:52
백준 13023번 ABCDE C++

서로 다른 5명이 이어져 있으면 된다. dfs로 문제를 해결하였는데, 처음에 방문 표시를 엉뚱한 곳에다 해서 시간이 좀 걸렸다. #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using ll = long long; bool isAns = false; vector v(2001, vector()); vector visited(2001, false); void Dfs(int n, int cnt) { if (cnt == 4) { isAns = true; return; } visited[n] = tr..
알고리즘 2022. 3. 14. 13:20
이전 Prev 1 ··· 62 63 64 65 66 67 68 ··· 83 Next 다음