본문 바로가기

전체 글

10166 관중석 모든 각을 저장하면 될 것 같았다. 1이면 360 2면 180 360 이렇게 각이 나오는데 길이가 360인 배열을 만들어두고 관중석이 있는 각을 1로 체크한 뒤 1의 개수만 세면 될 줄 알았다. 하지만 틀렸다. 생각해보니 2000까지 수가 들어올텐데 360 / 2000하면 소숫점이 나올테고 실수를 저장하긴 어렵다고 생각됐다. 그래서 그 다음으로 분수 자체를 저장하려고 했다. 4등분 한 수를 저장하려고 하면 1/4 2/4 3/4 4/4를 저장할 수 있는데 여기서 2/4, 4/4를 2로 나누면 1/2, 2/2가 된다. 이렇게 기약분수 꼴로 만들었을 때 그 분수를 저장해두고 중복인지 아닌지 체크해주면 된다. 기약분수는 최대공약수로 나누면 되니깐 gcd함수를 따로 만들었고 분수 저장은 2차원 배열로 만들어 i가.. 더보기
1568 새 새의 수가 10^9라 어떻게 하지 고민.. 고민하다가 숫자의 누적 합을 사용하면 되겠다 싶었고 또 그걸 나열해보니 뭔가 이진수 계산 같았다. 십진수 17을 이진수로 만드려면 17에서 16빼고 1빼면 되니깐 10001이 된다. 그것처럼 14를 구하기 위해서 10을 빼고 3을 빼고 1을 뺴면 되지 않을까.. 그래서 먼저 누적합을 저장하는 배열을 만들고 그 다음에 가장 큰 수 부터 빼기 시작했다. 그런데 문제는 5 같은 경우는 3, 1, 1 이렇게 1을 두 번 빼야한다. 그래서 숫자를 한 번 빼고 나서 다시 한 번 더 체크할 수 있게 했다. #include #include #include #include #include #include #include #include #include #include #defi.. 더보기
16199 나이 계산하기 만 나이만 조건 잘 달아주면 쉽게 구할 수 있다. #include #include #include #include #include #include #include #include #include #include #define xx first #define yy second #define all(x) (x).begin(), (x).end() using namespace std; using i64 = long long; using ii = pair; using ii64 = pair; int main() { int p1[3]; scanf("%d %d %d", &p1[0], &p1[1], &p1[2]); int p2[3]; scanf("%d %d %d", &p2[0], &p2[1], &p2[2]); int ag.. 더보기
17300 패턴 으으 조금 더 깔끔하게 짤 수 있을 것 같은데 생각이 안 난다. 그래서 조건 하나하나 확인 했다,, 이전에 이 문제 본 적 있는데 그 때는 어떻게하지 고민하다가 막혔는데 드디어 해결했네 #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define xx first #define yy second #define all(x) (x).begin(), (x).end() using namespace std; using i64 = long long int; using ii = pair; using iis = pair; using ii64 =.. 더보기
15900 나무 탈출 어떻게 풀지 그려봤을 때 트리의 높이의 합이 짝수면 형석이가 이기고 홀수면 성원이가 이긴다. 그래서 트리의 높이를 구하는 게 관건인데.. 생각 1 bfs를 쓰자 안 써서 써보고 싶었음.. 하지만 bfs를 쓰면 리프노드를 못 찾으니 리프노드까지의 길이를 알지 못한다. 생각 2 dfs 다음 노드가 존재하지 않으면 리프노드란 뜻이므로 리프노드를 찾을 수 있다. 그럼 리프노드의 길이의 합을 구할 수 있다 생각 3 그런데 이거 리프노드 길이의 합으로 생각 안 하고 그냥 전체 edge의 개수라고 생각하면 되지 않나??? 줄 수 세면 되는 거 아냐???? 아니었다고 한다 --미완-- 음... size가 0인거 출력해보니 1이 나온다. 왜지?? 나중에 찾아보기로 #include #include #include #inc.. 더보기
11058 크리보드 #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define xx first #define yy second #define all(x) (x).begin(), (x).end() using namespace std; using i64 = long long int; using ii = pair; using iis = pair; using ii64 = pair; using iii = tuple; int main() { int n; scanf("%d", &n); vector dp(n + 1); dp[1] = 1; dp[2] = 2; d.. 더보기
12738 가장 긴 증가하는 부분 수열 3 생각주간에 가장 긴 증가하는 부분수열 문제 있는 거 보고 이번에는 NlogN으로 푸는 거 공부해서 적용해야겠다!! 싶었는데 합이 가장 큰 걸 구하라고 해서 다른 문제로 제출했다. 이 알고리즘 세 번 봤는데 세 번 다 이해 못해서 낑낑거리다가 드디어 이해했다. 이제는 좀 알겠음. #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define xx first #define yy second #define all(x) (x).begin(), (x).end() using namespace std; using i64 = long long .. 더보기
6612 개미의 이동 개미가 부딪히고 방향을 바꾸는 걸 다르게 생각해보면 통과한다고 볼 수 있다. 그러면 최대 길이를 구할 수 있는데 마지막 개미의 번호를 구하는 게 문제였다. 느낌 상 중간에 있는 개미가 가장 늦게 떨어질 것 같은데 그러면 R R R인 경우에는 어떻게 해야 하나 싶고. 고민하다가 이 분 글 보고 참고해서 문제 풀었다. codersbrunch.blogspot.com/2017/02/6612-andrew-ant.html 6612번: Andrew the Ant https://www.acmicpc.net/problem/6612 $O(ta\lg a)$ 두 개미가 부딪혔을 때, 두 개미 모두 방향이 바뀌므로 서로를 통과해서 진행한다고 봐도 된다. 이런식으로 생각했을 때 모두 떨어지는데까지 걸린 시간은 codersbrun.. 더보기

티스토리툴바