꾸준함

문제 링크입니다: https://www.acmicpc.net/problem/11399 매우 쉬운 그리디 문제였습니다.돈을 인출하는데 걸리는 시간이 짧은 사람부터 정렬을 한 다음에 총 소요시간을 더해주면 경과시간이 최소가 됩니다! #include #include using namespace std; const int MAX = 1000; int N; int person[MAX]; int main(void) { cin >> N; for (int i = 0; i > person[i]; sort(person, person + N); //오름차순 정렬을 하면 최소 시간 int time = 0; for (int i = 0; i < N; i++) for (int j = 0; j

문제 링크입니다: https://www.acmicpc.net/problem/14502 브루트 포스와 BFS(Breadth First Search)를 적절히 이용하여 풀어야하는 문제였습니다.기존 연구소의 빈칸에 벽 세개를 세울 수 있는 모든 경우의 수를 고려해야하기 때문에 조금 까다로운 문제였습니다. 알고리즘은 아래와 같습니다.1. 연구소의 모든 칸을 확인하면서 빈칸이 있다면 벽을 세운 뒤 해당 칸의 벽은 고정인 상태로 무작위의 두 빈칸에 벽을 설치합니다.2. 추가한 벽의 개수가 3개가 되면 BFS 함수를 호출해 바이러스를 확산시킨 뒤 빈칸의 개수를 파악합니다.3. 모든 경우의 수를 계산한 다음 제일 많은 빈칸이 나왔던 경우의 빈칸의 개수를 출력합니다. #include #include #include us..

문제 링크입니다: https://www.acmicpc.net/problem/2662 최대 이익과 함께 각 회사에 얼만큼 투자를 했는지를 구해야하는 문제였기 때문에 조금 까다로웠던 문제였습니다.최대 이익을 구하는 것은 쉬웠습니다.언제나처럼 종만북 스타일로 재귀함수를 작성하여 각 회사마다 (0~현재 보유하고 있는 금액)만큼 투자를 진행하면서 최대 이익을 구했습니다. 각 회사에 투자한 금액을 구하는 방법은 아래와 같습니다.1. 다음 회사에 money만큼 투자했을 때 현재 기대하고 있는 최대이익(result)보다 큰 이익이 산출되면 result를 갱신하고 invested[investMoney][companyNum]에 투자한 금액인 money를 저장합니다.2. 1부터 M까지의 회사를 순회하면서 invested[현..

문제 링크입니다: https://www.acmicpc.net/problem/1783 아래와 같이 4가지의 경우로 나누어서 생각하면 됩니다.1. 세로가 1일 경우 움직이지 못하므로 1칸(시작하는 칸도 센다고 문제에서 명시)2. 세로가 2일 경우 2번과 3번의 조건을 최대 3번까지 이용 가능3. 세로가 3 이상일 경우i) 가로가 6 이하이면 1번과 4번 그리고 2번 혹은 3번 사용해서 최대 4칸ii) 가로가 7 이상이면 2번과 3번을 한번씩 사용하고 나머지는 1번과 4번 핵심은, 4회 이상 움직일 때 조건 1번~4번을 적어도 한번씩은 사용해야한다는 것이였습니다! #include #include using namespace std; int N, M; int main(void) { cin >> N >> M; i..

문제 링크입니다: https://www.acmicpc.net/problem/5567 DFS(Depth First Search)를 이용해서 1번의 친구와 친구의 친구를 구하는 문제였습니다.주의할 점은 마지막에 친구를 셀 때 자기자신까지 세지 않도록 for문을 2번부터 시작해야한다는 점이였습니다! #include #include using namespace std; const int MAX = 500 + 1; vector friends[MAX]; bool friendsList[MAX]; void findFriends(int nodeNum) { //nodeNum의 친구 파악 for (int i = 0; i < friends[nodeNum].size(); i++) { int next = friends[nodeN..

문제 링크입니다: https://www.acmicpc.net/problem/1068 parent 배열의 first는 부모노드 번호를 저장하고 second는 자신이 leaf인지 여부를 저장하도록 했습니다.사실 true일 때 leaf이면 더 직관적이겠지만 배열을 생성할 때 default 값은 false이므로 false일 때 leaf이도록 하였습니다. ancestor 배열은 자신의 부모를 포함한 모든 조상을 저장하게 하여 자신의 조상 중 deleteNode가 있을 경우 삭제되었다고 판단하여 다시 leaf가 아니라고 판단하였습니다.조상을 파악한 뒤 deleteNode를 제외한 모든 노드의 부모를 다시 확인하는 이유는 삭제된 노드의 부모는 leaf라고 main 문에서 판단하였는데 삭제된 노드의 부모가 다른 자식이..

문제 링크입니다: https://www.acmicpc.net/problem/11404 플로이드 알고리즘을 사용하면 쉽게 풀리는 문제였습니다.정식 명칭이 플로이드-와샬 알고리즘인 것은 오늘 처음 알았네요. 간단하게 플로이드 알고리즘을 설명하자면 from에서 to로 곧장 가는 것보다 via를 통해 가는 것이 더 빠를 경우를 찾는 알고리즘입니다.코드를 보면 쉽게 이해할 수 있을 것입니다!(실행속도 향상을 위해 중간 중간 continue문을 넣었습니다.) #include #include using namespace std; const int MAX = 100 + 1; const int INF = 100000 + 1; int N, M; int graph[MAX][MAX]; void floyd(void) { //v..

문제 링크입니다: https://www.acmicpc.net/problem/2698 문제에 공식이 제공되었기 때문에 매우 쉬운 DP 문제였습니다.주의할 점은 s1이 0으로 시작할 수도 있고 1로도 시작할 수도 있기 때문에 두 경우의 수를 모두 더해줘야한다는 점입니다! #include #include using namespace std; const int MAX = 100 + 1; int N, K; int cache[MAX][MAX][2]; //N, K, 0 or 1 int numOfSequence(int len, int total, int bit) { //기저 사례 if (len >= N || total > K) return 0; //조건 충족 if (len == N - 1 && total == K) r..

문제 링크입니다: https://www.acmicpc.net/problem/1563 매우 쉬운 DP 문제였습니다.0일부터 시작해서 다음날 출석, 결석, 지각하는 3가지의 경우의 수를 고려해주면 되는 문제였습니다.주의할 점은 3번 연속 결석해야지 개근상이 아니므로 출석과 지각하는 날에는 결석 횟수를 0으로 초기화 해줘야합니다!그런데 무슨 학교가 결석보다 지각을 더 문제 삼는지 모르겠습니다... #include #include #include //memset using namespace std; const int MOD = 1000000; const int MAX = 1000 + 1; int N; int cache[MAX][MAX][3][2]; //길이, 출석, 결석 연속, 지각 int fullAttenda..

문제 링크입니다: https://www.acmicpc.net/problem/2533 알고리즘 자체는 쉬운 문제였는데 구현하는데 애를 먹었던 문제였습니다.getEarlyAdaptor 함수 내에서 DFS를 같이 병행하려다 보니까 재귀가 돌면서 안에서 코드가 꼬인 것 같습니다.그래서 DFS와 getEarlyAdaptor 함수를 불리하고 DFS를 통해 양방향 그래프를 단방향 그래프로 바꾼 뒤 답을 구했더니 잘 구해졌습니다.여기서 단방향 그래프로 바꾸는 이유는 루트로부터 잎 노드(leaf node)까지 단방향으로만 확인하기 때문입니다. 알고리즘은 아래와 같습니다.1. 본인이 얼리어댑터라면 자식은 얼리어댑터여도 좋고 아니여도 좋습니다.2. 본인이 얼리어댑터가 아니라면 자식은 무조건 얼리어댑터여야 합니다. #incl..