알고리즘 (14) 썸네일형 리스트형 [백준 1911] 흙길 보수하기 www.acmicpc.net/problem/1911 1911번: 흙길 보수하기 어젯밤 겨울 캠프 장소에서 월드 본원까지 이어지는, 흙으로 된 비밀길 위에 폭우가 내려서 N (1 > N >> L; for(int i = 0; i > M_st; cin >> M_fi; pair pTmp = make_pair(-M_st, -M_fi); prior_Que.push(pTmp); } while(!prior_Que.empty()) { pair pTmp = prior_Que.top(); prior_Que.pop(); if(-pTmp.first > Pos) Pos = -pTmp.first; while(-pTmp.second > Pos) { Pos += L; cnt++; } } cout [백준 17938] 퐁당퐁당2 www.acmicpc.net/problem/17938 17938번: 퐁당퐁당 2 이 경우에 입력 예시의 경우 사람이 5명이고 휘수는 4번에 위치한다. 5번째 턴에서 1번사람 양팔, 2번사람 양팔, 3번사람의 왼팔이 필요한데 휘수가 끼어들 수 없기 때문에 트롤에 실패한다. www.acmicpc.net 이번 문제는 완전히 수학적인 사고를 통해 풀어야하는 문제이다. 저는 전체적으로 큰 로테이션인 (1 ~ 2N ~ 2)를 하나의 큰 로테이션 루틴으로 잡고 풀었다. 한 루틴을 돌때, 쓰이는 손의 개수는 (1 ~ 2N ~ 2) = (1 ~ 2N) + (1 ~ 2N) - 1 - 2N 이다. (2N 과 1 은 중복되지 않기 때문!!) 여기서 1~2N의 총합은 (1+2N) * N이다. (가우스가 푼 방식을 이용) 게다가.. [백준 17838] 커맨드 www.acmicpc.net/problem/17838 17838번: 커맨드 T개 각각의 테스트 케이스에 대해 윤표가 좋아하는 커맨드이면 1, 그렇지 않으면 0을 한 줄에 하나씩 출력한다. www.acmicpc.net 이문제는 3가지 조건을 만족하는 문자열인지를 판단하는 문제로 상대적으로 난이도가 그렇게 어렵지 않았던 문제이다. 조건 1. 길이가 7 2. 문자 종류가 2가지 3. 커맨드 순서가 AABBABB 처음에는 2번조건이 testcase3 처럼 문자열이 2종류 이상만 고려했다가 모두가 다 같은 경우를 고려하지 못하고 틀렸었다. 그래서 문자열을 비교하는 조건중에서 맨 마지막인 조건 0번 index와 6번 index 문자열이 달라야하는 조건을 통해 2번조건을 지킬 수 있었다. #include using .. [백준 2578] 빙고 www.acmicpc.net/problem/2578 2578번: 빙고 첫째 줄부터 다섯째 줄까지 빙고판에 쓰여진 수가 가장 위 가로줄부터 차례대로 한 줄에 다섯 개씩 빈 칸을 사이에 두고 주어진다. 여섯째 줄부터 열째 줄까지 사회자가 부르는 수가 차례대로 �� www.acmicpc.net 이문제는 처음에는 맵을 입력받고 하나씩 지워나가면서 우리가 늘 하던 익숙한 빙고게임과 똑같다 3 Bingo를 하면 게임에서 승리하며 그때까지 몇번에 도달하는지이다. 처음에 2차 for 문은 맵을 만드는 블록이고 맵은 두가지로 5x5로 글로벌 변수로 선언한 애는 빙고의 유무를 알려주고 1차원으로 된 맵은 구조체를 통해 숫자에 맞춰 어디 위치에 있는지를 나타내는 변수이다. 이러한 1차원 맵은 실제로 빙고문제로 풀때 적극 활.. [백준 11048] 이동하기 www.acmicpc.net/problem/11048 11048번: 이동하기 준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다. 준규는 �� www.acmicpc.net 이문제는 모든 경우의 수를 다루는 DP(Dynamic Programming) 알고리즘을 사용하여 풀 수 있다. 처음에 나의 접근 방법은 데이터를 다 받은 뒤에, 시작에서 끝으로 퍼져나가는 방식을 고려하여 풀려고 했다. 처음 코드 #include using namespace std; #define MAX_SIZE 1000 int g_nMap[MAX_SIZE][MAX_SIZE]; int Maxi.. [백준 15903] 카드 합체 놀이 www.acmicpc.net/problem/15903 15903번: 카드 합체 놀이 첫 번째 줄에 카드의 개수를 나타내는 수 n(2 ≤ n ≤ 1,000)과 카드 합체를 몇 번 하는지를 나타내는 수 m(0 ≤ m ≤ 15×n)이 주어진다. 두 번째 줄에 맨 처음 카드의 상태를 나타내는 n개의 자연수 a1, www.acmicpc.net 이문제를 보았을 때 자료구조중 priority queue를 사용하여 풀면 쉬운 모델이다. 그래서 단순이 c++ 에 내장된 priority queue를 사용하기 보다 이컨셉에 맞춰 직접 구현하면서 문제를 풀어보았다. 코드는 다음과 같으며 기존의 힙구조를 사용한 priority queue와 다르게 linked list 구조의 priority queue를 만들어 해도 충분할꺼 같.. 이전 1 2 다음
