막대기에 맨 오른쪽부터 탐색한다. 어떤 막대기보다 왼쪽에 있는 막대기는 가려져서 보이지 않는 것에 유념하자. 처음에 여기서 틀렸다. #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

분리 집합 분리 집합을 이용해 풀었다. 분리 집합의 기본을 연습하고 싶다면 이 문제를 풀어보자 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; ..

연쇄 행렬 곱셈 일반적으로, i * j 행렬과 j * k 행렬을 곱하면 원소단위 곱셈의 실행 횟수는 다음과 같다. i * j * k 번 실행 횟수가 행렬의 크기에 따라 결정된다. 따라서 최적의 순서도 행렬의 크기에만 의존한다. n개의 행렬 \({A}_{1}\) ... \({A}_{n}\))을 곱하는 모든 순서의 가지 수를 \({T}_{n}\)이라고 하자. A1을 마지막으로 곱하는 순서의 집합의 가지수는 \({T}_{n-1}\)이다. (A_1...A_n까지 곱하는 서로 다른 순서의 가지수) An을 마지막으로 곱하는 순서의 가지 수 또한\({T}_{n-1}\)일 것이다. 따라서 다음과 같은 부등식이 나온다. $$T_n >= T_{n-1} +T_{n-1} = 2 * T_{n-1}$$ 두 개의 행렬을 곱하는 법..

이해 수학 문제다. Josephus problem은 wiki에도 잘 나와있다. https://en.wikipedia.org/wiki/Josephus_problem Josephus problem - Wikipedia From Wikipedia, the free encyclopedia Jump to navigation Jump to search In computer science and mathematics, the Josephus problem (or Josephus permutation) is a theoretical problem related to a certain counting-out game. A drawing for the Josephus problem en.wikipedia.org 1에서 인..

이해 입력 D의 범위 안에서 최대 점수('현재 점수 * 다음 점수'의 합)을 구한다. 입력받은 2차원 배열과 같은 크기의 dp[i][j]를 만들자. dp[i][j]가 i행 j열 까지의 최대 점수라고 할 때, dp[i][j]는 i행 j열로 가기 전 단계 x행 y열에서, 'x행 y열의 점수 * i행 j열의 점수' 연산을 더하는 값과, 더하지 않는 값 중의 최댓값이다. 따라서 dp[i][j] = max(dp[i][j], dp[x][y] + cur*next); 라는 점화식을 떠올리는 것은 쉽다. 틀렸습니다 70%쯔음에서 '틀렸습니다'를 받았다면 INF(dp배열 또는 답의 초기값의 최저)의 값을 너무 낮게 설정했을 수 있다. 메모리 초과가 났다면 입력의 2차원 배열을 int arr[100001][100001]로 ..

https://www.acmicpc.net/problem/17398 17398번: 통신망 분할 첫 번째 줄에는 통신탑의 개수인 자연수 N, 통신탑 사이의 연결의 개수인 자연수 M, 통신망 연결 분할 횟수인 자연수 Q가 공백으로 구분되어 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ M ≤ 100,000, 1 ≤ Q www.acmicpc.net 아이디어 union find인데 제거할 때 나오는 비용을 세는 대신, 전부 분리한 다음 분리하지 않을 간선만 이은 채로 union을 전부 돌면 된다. 전부 서로소 집합인 상태에서 끊지 않을 간선을 제외한 노드들(예제에서는 1,2)을 union할때와 이후 답을 찾기위한 union은 같으나 후자에서는 부모노드 확인과정을 거친 후 비용을 곱해서 저장해야 한다. 아이디..