synodic의 삭망월

2021.10.27 - [PS/백준] - 백준 1005 (C++) ACM Craft 백준 1005 (C++) ACM Craft https://www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총. synodic.tistory.com ACM Craft와 유사. https://www.acmicpc.net/problem/1516 1516번: 게임 개발 첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다. ..

https://www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 아이디어 위상정렬. 근데 약간의 다이나믹 프로그래밍을 곁들인... 위상정렬을 아는 사람이라면, 문제를 보고 위상 정렬 진행해서 같은 노드로부터 출발하면 큰 값의 delay(d[i]) 를 더하면 되겠구나, 하고 생각했을 것이다. 현재 노드를 cur, cur의 다음 노드를 nxt라고 했을때 result[nxt] 는 result[cur] + d[nxt] 중 최댓값이다. 틀렸습니다 를 받았다면? 1..

막대기에 맨 오른쪽부터 탐색한다. 어떤 막대기보다 왼쪽에 있는 막대기는 가려져서 보이지 않는 것에 유념하자. 처음에 여기서 틀렸다. #include #include using namespace std; using ll = long long; int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n,stick,ans=1; cin >> n; int arr[100000]; for (int i = 0; i > arr[i]; } stick = arr[n-1]; for (int i = n-1; i >= 0; i--) { if (arr[i] > stick) { // 가려지는 높이 갱신 ans++; stick = a..

아이디어 풀면서 재밌었던 구현 문제다. 숫자가 최대 100자리까지 주어진다고 했으므로 우리가 알고 있는 일반적인 변수크기로는 택도 없다. 따라서 string으로 a, b 변수를 만들고 어떻게 연산할 것인지 고민해보자. 우선 곱셈은 간단하다. 곱셈은 자릿수끼리의 덧셈이므로 string a와 b의 size(또는 length)의 덧셈만큼 0을 출력하면 된다. 덧셈에서는 경우의 수가 세가지이다 1. a > b 2. a < b 3. a == b 1. 의 경우 a.size() - b.size() - 1만큼 자릿수(0)를 출력한다. 2. 의 경우도 1과 마찬가지이다. 3. 의 경우는 "2"를 출력하고 수의 자릿수 -1만큼 "0"을 출력하면 된다. 코드 #include #include #include #include ..

https://www.acmicpc.net/problem/20040 20040번: 사이클 게임 사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n − 1 까지 고유한 www.acmicpc.net 아이디어 분리집합을 알면 날먹 가능한 문제 이 유형이 대체로 티어가 높게 잡혀 날먹하기 좋다 입력받는 두 노드를 merge하기 전 사이클이 생기는지 확인한다. 사이클이 생긴다면 그대로 그때의 iteration(> n >> m; for (int i = 0; i a >> b; if (getParent(a) =..

아이디어 인접행렬 adj에 입력 받을 때, 갈 수 없는 경로를 0의 값을 INF (아주 큰 값)으로 바꿔 저장하고 플로이드 와샬로 adj를 탐색하면서 다른 노드를 통해 거쳐갈 수 있는 빠른 길이 있다면 갱신해주었다. 코드 #include #include #include using namespace std; using ll = long long; const int INF = 1e8; const int MAX = 101; int n, ans=0; int adj[MAX][MAX]; void fw() { for (int k = 1; k

미치겠다... 부산 놀러가서 또 까먹었다. 이번에도 문제 미리 풀고 코드 복사해갔는데ㅋㅋㅋ 빼먹은 날 전부 어딘가에 여행 간 날이다. 처음은 강릉, 나중은 부산 솔브닥에 무슨 재화 시스템이 생겼나보다 두근두근 1일 1솔하는 보람이 조금 생길지도 3학년 2학기 전공을 너무 널널하게 들었나 4전공인데 여유롭다... 그 어느 학기보다 여유로워서 덕분에 매일 백준 풀고 관심있는 거 찾아보고 그런다. 1학년때는 전과하려고 학점 따느라 바빴고 2학년때는 부전공 시작하면서 갑자기 상승한 전공 난이도에 우왕좌왕하고 3학년 1학기때는 갑자기 전공공부가 재밌어지긴 했지만 프언 과제가 쏟아져서 눈 감았다뜨니 종강이었는데... 요새는 정말 비싼 호텔도 (내돈내산은 아니지만) 다녀왔고 음 매일 메뉴 고를 때도 메뉴판 옆에 적힌..

분리 집합 분리 집합을 이용해 풀었다. 분리 집합의 기본을 연습하고 싶다면 이 문제를 풀어보자 2021.09.28 - [PS/백준] - 백준 1717 (C++) 집합의 표현 백준 1717 (C++) 집합의 표현 크루스칼 알고리즘은 모르는 이에게 설명하기도 쉽고 이해하기도 쉽다. unionParent함수에서 일반적으로 부모노드가 더 큰 쪽에 합치지만 일방적으로 첫번째 파라미터인 변수에 union 했다. 코드 // synodic.tistory.com 시간 비교(BFS vs Union set) 찾아보니 이분탐색 + bfs를 이용한 방법이 많다. 맨 위가 나의 제출인데 굉장히 적은 시간과 메모리가 걸린 것으로 보인다. 처음엔 주어진 집합을 전부 union하고 각각의 비용을 2차원 인접 행렬에 저장한 뒤 입력의 ..

이해 분리 집합으로 풀면 된다. i,j를 union하고 m개의 첫번째와 입력받는 m-1개가 연결되었는지 확인한다. 틀렸습니다 92%에서 계속 틀리길래 한참 고민했는데 디버깅 해보니 아니 나는 무슨... union 해주는 과정에서 Parent를 초기화해서...(왜? 아마 코드 줄이려고 그런 흐린 판단을 했던 것 같다...) 내가 한 실수 이외에도 계속 AC를 못 받는다면 index를 1부터 저장해보는 것도 방법일 수 있다. 질문 검색해보니 그런 케이스가 좀 있는 것 같았다. 코드 #include #include #include using namespace std; using ll = long long; const int MAX = 210; const int INF = 987654321; int n, m; ..

탐색 종료의 기준을 잡는다. 내가 짠 코드는 어떤 행의 모든 열을 우선적으로 탐색하기 때문에 행이 n(체스판의 크기)가 되었을때 종료한다. 어떤 열 i, 어떤 행 j에 있다고 하자. 그 좌표를 기준으로 같은 열, 대각선에 위치하지 않으면 그 좌표를 체크해준다. 이 과정을 반복해서 종료조건에 도달했을 경우 가능한 체스판 경우를 +1해준다. #include #include #include using namespace std; #define MAX 40 int n; int cnt = 0; bool isused1[MAX]; // 같은 열 bool isused2[MAX]; // 우상 대각 bool isused3[MAX]; // 좌상 대각 /* i는 열, j는 행 */ void solve(int j) { if(j ..