본문 바로가기

전체 글

6373 Round and Round We Go 풀어보려다가 문자열 곱셈 구해야 해서 패스,, ㅠㅠ #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; bool solve(i64 n) { string s1 = to_string(n); for (int i = 1; i 더보기
17425 약수의 합 N보다 작은 약수들의 합 어떻게 구할지 그려보니 N이 10이라 한다면 1은 10번 2는 5번 ... 이런 규칙이 보였다. 그래서 1부터 10^6까지의 모든 수를 다 미리 구하고 그 수의 합을 구한 뒤 하나씩 출력했다. #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; i64 calc[1000005]; i64 sum[100000.. 더보기
2981 검문 나머지가 같게 되는 M을 찾는 문제 느낌상 모두 M으로 나눠야 하니 M이 모든 수의 약수가 되어야 된다고 생각했는데 나머지가 있는 게 문제였다. 이전에 이런 숫자? 다루는 문제는 숫자끼리 빼야 한다는 걸 풀어봐서 뺐더니 나머지가 같다면 나머지가 없어진다는 것을 알 수 있었다. 그래서 숫자를 뺀 후 그 수들의 최대공약수를 구하고 최대공약수의 약수를 출력하게 해서 풀 수 있었다. 문제 풀면서 생각없이 인접한 수만 빼서 구했는데 사실 왜 전부를 빼서 구하지 않을까를 고민했어야 했다ㅋㅋ 예를 들어 x2 - x1이 a 이고 x3 - x2가 b라면 a도 m의 배수이고 b도 m의 배수가 된다. 그럼 x3 - x1 = a + b가 돼서 이것 또한 m의 배수이다. 그래서 m을 결정하는 최소 단위가 인전합 애들의 차라서 .. 더보기
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.. 더보기

티스토리툴바