본문 바로가기

전체 글

1916 최소비용 구하기 다익스트라 연습 문제로 풀어보고 싶었다. #include #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 n, d; vector edge; vector Dijkstra(int sta.. 더보기
다익스트라 조금 더 정리가 필요할 것 같다.. 입력 첫 줄에 정점의 개수 N과 간선의 개수 M, 그리고 시작 정점 S가 주어집니다. 다음 M줄에 간선의 관계 시작정점 u와 도착정점 v 그리고 간선 가중치 w가 주어집니다. 7 11 1 1 2 4 1 3 10 1 7 20 2 3 4 2 4 3 3 5 7 4 3 11 5 7 4 6 5 1 7 6 10 6 4 2 출력 시작정점에서 각 정점사이의 거리를 모두 출력합니다. 0 4 8 7 15 29 19 #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define xx first #d.. 더보기
3144 자석 어려웠다...! 문제 이해는 했는데 이걸 그래서 어떻게...? 싶은 문제였다. 내가 이해한 내용 - 처음에 자석이 같은 방향이면 전부 합쳐짐 - 합쳐진 자석을 바탕으로 길이를 L로 맞추면 된다 - 중간에 있는 자석 뒤집으면 무조건 3개가 합쳐짐 - 양 끝에 있는 자석 뒤집으면 이건 2개면 합쳐짐 어... 이제... 어... 어떻게... 합치죠...? 그래서 역시나 북님의 도움 1. 배열에 부분합을 저장한다 sum[i] = 0...i번째 합 2. 만약 sum[i]가 X이고 sum[j]가 X - L이면, sum[i] - sum[j]는 L이다. 이런 i, j를 찾으면 됨!! 3. 그럼 반대로 pos(L) 이런 식으로 저장하자. sum[i] = L, pos(L) = i 이렇게 합을 기준으로 인덱스를 저장 그런데.. 더보기
16210 DSHS Bank 와 수학문제였다 택시거리 x / y 나눠서 생각하고 수식 풀어서 정리한 다음 부분합 + lower_bound 사용해서 풀어야 했다. 오늘 푼 골드1보다 더 어려웠다. #include #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 = p.. 더보기
18436 수열과 쿼리 37 구간..! 보고 세그트리인 걸 알았다. 세그트리 예전에 한 번 써보고 안 써봐서 적응하는데 시간이 조금 걸렸다. 아이디어는 생각외로 간단하다. 짝수는 0을 저장하고 홀수는 배열에 1을 저장한다. 그래서 구간합을 구하는데 홀수면 구간합 자체가 홀수의 개수가 되고 짝수면 구간 - 구간합을 하면 짝수의 개수가 나온다. #include #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 namespac.. 더보기
2873 롤러코스터 규칙 파악하는게 힘든 문제였다. 구현도... 별찍기 문제처럼 모든 경우 나눠가면서 풀어야 편하다. 아니면 뇌가.. 꼬여버려요.. 보면 판이 홀수 * 홀수 / 홀 * 짝 / 짝 * 홀 / 짝 * 짝 이렇게 4가지 경우가 있다. 하나라도 홀수라면 모든 배열을 다 지나갈 수 있는데 짝 * 짝인 경우가 문제였다. 이것도 어떻게 경우 나눠가며 풀었다.. 처음 짤 때 엄청 더럽게 짰는데 정리하고 짜니 완전 깔끔히 짰다. 뿌듯 #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define xx first #define yy second #de.. 더보기
16923 다음 다양한 단어 https://www.acmicpc.net/problem/16923 16923번: 다음 다양한 단어 다양한 단어란 모두 다른 알파벳 소문자로만 이루어진 단어를 의미한다. 예를 들어, "codeplus", "coding", "algorithm"은 다양한 단어, "baekjoon", "startlink"는 다양한 단어가 아니다. 다양한 단어 S가 주어졌 www.acmicpc.net 저번에 못 풀었던 ucpc 연습문제 미뤄두다가 오늘 드디어 푼다. 보자마자 개꿀 실버문제~ 라고 생각했는데 아앗 아니었다. 난 그냥 안 나왔던 알파벳 중 하나 끝에 붙이면 된다고 생각했는데 마지막 예제 보고 아니라는 걸 깨달았다. 으으음... abc인 경우는 앞의 알파벳이 다 찼으니 새로운 d를 붙여야 하고.. codeplus인 .. 더보기
20149 선분 교차 3 으으으 구현 열심히 했는데 실수가 있었는지 틀렸다. 누더기 된 코드 확인하는 것보다 멀끔한 북님 코드 분석하는게 더 좋을 것 같아서 개쓰래기 코드를 들고 오지는 않겠다. 아래는 북님 코드 전문이고 이제 분석도 해보자 #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define all(x) (x).begin(), (x).end() #define xx first #define yy second using namespace std; template using pq = priority_queue; usi.. 더보기

티스토리툴바