전체 글 104

백준 10409 (C++) 서버

https://www.acmicpc.net/problem/10409 10409번: 서버 당신은 FCFS(First-Come, First-Served)의 규칙에 따라 요청된 일을 처리하는 서버를 담당하게 되었다. 매일, 당신은 일을 처리하기 위해 최대 T분 동안 서버에 시간을 할당할 수 있다. 당신은 오늘 주어 www.acmicpc.net 여태 합한 시간(sum)과 이번에 입력받은 job의 시간의 합이 T를 넘어설 때, 이터레이션 i 를 출력하고 main을 종료한다. main을 종료하지않고 반복문을 빠져나왔다면, 모든 일이 시간 안에 끝난 것이므로 n을 출력한다. #include using namespace std; using ll = long long; const int MAX = 100001; int ..

PS/BOJ 2021.11.07

백준 1516 (C++) 게임 개발

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개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다. ..

PS/BOJ 2021.10.28

백준 1005 (C++) ACM Craft

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..

PS/BOJ 2021.10.27

백준 17608 (C++) 막대기

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

PS/BOJ 2021.10.23

백준 2935 (C++) 소음 (출력 초과, 틀렸습니다)

아이디어 풀면서 재밌었던 구현 문제다. 숫자가 최대 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 ..

PS/BOJ 2021.10.20

백준 20040 (C++) 사이클 게임

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) =..

PS/BOJ 2021.10.19

백준 11403 (C++) 경로 찾기

아이디어 인접행렬 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

PS/BOJ 2021.10.18

10.17 최장 스트릭 또 놓침 (부제: 1일 1솔의 어려움)

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

생활/일상 2021.10.17

백준 1939 (C++) 중량제한 (메모리 초과 -> 4496KB, 시간-32ms)

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

PS/BOJ 2021.10.15

백준 1976 (C++) 여행 가자 (틀렸습니다, 까닭)

이해 분리 집합으로 풀면 된다. 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; ..

PS/BOJ 2021.10.14