목록백준 (475)

1일1알

백준 2302 극장 좌석 C++

일단 고정된 좌석은 없다고 가정하고 좌석에 앉을 수 있는 수를 구해보면 1일때는 (1) 1가지이다. 2일때는 (1, 2), (2, 1) 2가지이다. 3일때부터 규칙을 찾을 수 있다. 만약 마지막 좌석인 3을 그대로 둔다면 3은 고정된 상태에서 1, 2만 움직일 수 있다. -> 2일때의 경우 3을 움직인다면 (3, 2) 가 고정된 상태에서 1만 움직일 수 있다. -> 1일때의 경우 그러므로 구할 수 있는 점화식은 dp[n] = dp[n-1] + dp[n-2] 이다. 고정된 좌석이 있을 때에는 고정된 좌석을 기준으로 다른 문제라고 생각하고 구한 답들을 곱해주면 된다. 위의 예제의 경우에는 고정된 좌석을 기준으로 3개, 2개, 2개로 나뉘어졌으므로 dp[3] * dp[2] * dp[2] 이다. #include..
알고리즘 2021. 12. 10. 12:02
백준 2251번 물통 C++

dfs방식을 이용해서 탐색하면서 A에 있는 물의 양이 0일 때 C에있는 물의 양을 저장해가면서 문제를 해결하였다. 탐색을 이미 했는지 확인하는 visited 은 A, B, C 중 2개만 검사하면 나머지는 값이 고정되기 때문에 visited 배열을 2차원 배열로 사용하였다. #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; int visited[201][201] = { false }; int A, B, C; set ans; void solve(int a, int b, int..
알고리즘 2021. 12. 9. 13:05
백준 1446번 지름길 C++

D까지 가는 최소 거리를 구하는 문제이다. 역주행은 불가능하다. dp방식으로 해결하였다. 처음에는 거리를 지름길을 고려하지 않고 초기화해주고 지름길들의 도착 위치를 기준으로 정렬한 뒤, 도착 전의 위치들을 검사하면서 도착 위치까지의 최소 거리를 찾아서 지름길을 이용한 최소 거리들을 구하고, 마지막에는 처음부터 D까지 검사하면서 최소 거리를 찾는 방식으로 문제를 해결하였다. 풀고 나서 시작 위치를 기준으로 정렬해도 맞았는데, 이유는 잘 모르겠다. #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef l..
알고리즘 2021. 12. 8. 12:28
백준 5904번 Moo 게임 C++

moo 문자열을 간단하게 숫자로 나타내 보겠다. moo는 3, mooo는 4, mooooo는 5 이런 식으로 사용할 것이다. moo 수열은 3 -> 3 4 3 -> 3 4 3 5 3 4 3 이런 식으로 증가하게 된다. n을 입력받아서 n이 수열의 길이보다 크다면 수열의 길이를 규칙에 맞춰서 늘리고, n이 수열의 길이보다 작다면 n의 값을 재조정하고 수열의 길이를 축소해가면서 문제를 해결하였다. 처음에는 직접 수열을 구현해보았는데, 그런 식으로 문제를 풀면 메모리 초과가 난다. 따라서 규칙에 맞춰서 특정 위치의 문자를 구하는 식으로 문제를 해결해야 한다. #include #include #include #include #include #include #include #include #include #inc..
알고리즘 2021. 12. 7. 12:31
백준 15662번 톱니바퀴 (2) C++

회전시킬 톱니바퀴와 회전 방향을 입력받고 해당 톱니바퀴는 회전시킨 뒤, 회전시키기 전의 톱니바퀴와 맞닿아 있는 톱니바퀴가 같다면 맞닿아 있는 톱니바퀴는 회전시키지 않고, 다르다면 반대방향으로 회전시킨다. 이것을 반복하다가 회전이 끝났을 때 12시 방향에 있는 S극의 톱니바퀴의 개수를 구하는 문제이다. 문제를 푸는데 어려움은 딱히 없었던 것 같은데 시간은 조금 걸린 것 같다. 엄청 쉬운 문제는 아닌 것 같은데 단순히 구현만 하면 돼서 그런지 정답률이 73퍼센트나 된다는게 놀랍다. #include #include #include #include #include #include #include #include #include #include #include #include #include using names..
알고리즘 2021. 12. 6. 15:13
백준 2002번 추월 C++

들어간 차들은 벡터를 이용해 순서대로 문자열을 저장해서 들어간 순서로 차의 번호를 접근할 수 있게 만들었고, 나온 차들은 unordered_map 를 이용해 차의 번호로 나온순서를 접근할 수 있게 만들었다. 들어간 차들을 검사하면서, 자신보다 먼저 들어온 차들 중 하나라도 자기보다 늦게 나왔다면 추월을 한 것이다. 들어간 차들을 순서대로 검사하면서 그 차의 번호를 이용하여 나온 차들의 순서를 접근하여 비교하면 문제를 해결할 수 있다. #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long lo..
알고리즘 2021. 12. 5. 12:52
이전 Prev 1 ··· 75 76 77 78 79 80 Next 다음