https://www.acmicpc.net/problem/2240 2240번: 자두나무 자두는 자두를 좋아한다. 그래서 집에 자두나무를 심어두고, 여기서 열리는 자두를 먹고는 한다. 하지만 자두는 키가 작아서 자두를 따먹지는 못하고, 자두가 떨어질 때까지 기다린 다음에 떨어 www.acmicpc.net 1. Logic 먼저 DP테이블이 의미하는 것은 n초에 먹을 수 있는 자두의 최대 갯수이다. dp[자두떨어지는 시간][움직인횟수][위치한나무번호] 부분문제를 쪼개보자면 시작할때는 1. 1번 나무에서 시작하는 경우 2. 2번 나무에서 시작하는 경우 이후에는 1-1. 1번나무에서 받아먹고 계속 1번에 있는 경우 1-2. 1번나무에서 받아먹고 2번나무로 옮기는 경우 2. 2번나무에서 받아먹고 계속 2번에 있는 ..
Algorithm
https://www.acmicpc.net/problem/1138 1138번: 한 줄로 서기 첫째 줄에 사람의 수 N이 주어진다. N은 10보다 작거나 같은 자연수이다. 둘째 줄에는 키가 1인 사람부터 차례대로 자기보다 키가 큰 사람이 왼쪽에 몇 명이 있었는지 주어진다. i번째 수는 0보다 www.acmicpc.net 1. Logic for문을 0부터 돌기때문에 내 앞에 나오는 애들은 전부 나보다 키가 작다. 그래서 내 앞에 키 큰 사람이 몇명올지 그 사람들의 자리를 남겨 놓는게 목적이다. 2. Code #include using namespace std; int seat[10]; int main() { int n; cin >> n; for(int i = 0; i < n; i++) { //입력 받는 횟수..
https://www.acmicpc.net/problem/14891 14891번: 톱니바퀴 첫째 줄에 1번 톱니바퀴의 상태, 둘째 줄에 2번 톱니바퀴의 상태, 셋째 줄에 3번 톱니바퀴의 상태, 넷째 줄에 4번 톱니바퀴의 상태가 주어진다. 상태는 8개의 정수로 이루어져 있고, 12시방향부터 www.acmicpc.net 1. Logic 문제 요약 : 톱니바퀴와 맞닿아있는 톱니가 다른 극이면 톱니를 반대방향으로 움직이고 같은 극이면 톱니를 움직이지 않는다. 각 톱니별 부분 문제를 생각해보자면 회전방향 \ 톱니번호 1번 톱니 2번 톱니 3번 톱니 4번 톱니 시계방향 2번 > 반시계 3번 > 시계 4번 > 반시계 1번 > 반시계 3번 > 반시계 4번 > 시계 1번 > 시계 2번 > 반시계 4번 > 반시계 1번 >..
https://www.acmicpc.net/problem/2563 2563번: 색종이 가로, 세로의 크기가 각각 100인 정사각형 모양의 흰색 도화지가 있다. 이 도화지 위에 가로, 세로의 크기가 각각 10인 정사각형 모양의 검은색 색종이를 색종이의 변과 도화지의 변이 평행하도록 www.acmicpc.net 1. Logic 도화지의 사이즈가 최대 100*100이라고 했기 때문에 최악의 경우의 완탐을 돌아도 10000에 입력받는거까지 넉넉잡아도 1초안에는 무조건 계산이 가능하다. 처음 문제를 읽고 색종이의 갯수 n * 100에 중복 구간을 어떻게 빼줄까를 고민하다가 굳이 어렵게 생각해서 값을 빼주지 말고 그냥 한번만 세주면 되겠다는 생각을 했다. 입력 받은 좌표값에 +10까지 방문 처리를 해주고 갯수를 세..
https://www.acmicpc.net/problem/2012 2012번: 등수 매기기 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 500,000) 둘째 줄부터 N개의 줄에 걸쳐 각 사람의 예상 등수가 순서대로 주어진다. 예상 등수는 500,000 이하의 자연수이다. www.acmicpc.net 1. Logic 자기가 예상한 등수랑 다르면 불만도가 생기기 때문에 자신의 예상 등수를 입력받은후 정렬한다. 테스트 케이스로 예를 들면 1 5 3 1 2 > 1 1 2 3 5 1 ~ 5등까지 나오기 때문에 작은것부터 숫자를 맞춰주면 된다. 코드를 보면 더 이해가 잘 갈것이다. 2. Code #include #include #include using namespace std; vector vec; int ..
https://www.acmicpc.net/problem/1992 1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또 www.acmicpc.net 1. Logic 4등분을 해서 모든 칸이 일치하면 해당 칸의 번호를 출력하는 문제이다. 기본적인 분할 정복 문제이지만 출력을 할 때 한번 생각해야 되서 실버 1인듯?하다 기본적인 분할 정복 아이디어를 활용하여 풀이하면 되고, 출력은 분할하는 부분에서 즉 섞여있는 부분을 확인하려고 재귀를 들어갈 때 '('를 출력하고 들어가서 확인하고 나오면서 ')'를 출력해주면 된다. 2. Code #..
https://www.acmicpc.net/problem/1780 1780번: 종이의 개수 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다. 만약 종이가 모두 같은 수 www.acmicpc.net 1. Logic 대표적인 분할정복의 예제인 것 같다. N의 범위가 3^7이라고 했기 때문에 3^7=2187 넉넉잡아 배열의 크기를 2200으로 잡아줬다. 함수에 처음 들어가면 내가 지금 보고 있는 종이가 전부 같은 숫자로 이루어졌는지 확인 하고 하나라도 다르다면 다시 9등분으로 쪼개서 확인해 준다. 아래의 표는 코드의 주석과 대응되는 9등분 한 위치이다. 1 2 3 4 5 6 7 8 9..
https://www.acmicpc.net/problem/4779 4779번: 칸토어 집합 칸토어 집합은 0과 1사이의 실수로 이루어진 집합으로, 구간 [0, 1]에서 시작해서 각 구간을 3등분하여 가운데 구간을 반복적으로 제외하는 방식으로 만든다. 전체 집합이 유한이라고 가정하고, www.acmicpc.net 1. Logic 사이즈를 쪼개 들어가서 0일 떄 -를 출력하면 됨. 테스트 케이스를 보면 항상 n에서는 n-1의 모양이 두번 나온다. 그리고 사이 사이에는 3의 n제곱만큼 공백이 있다 분할 정복 공부할 때 처음 풀어보면 좋은 문제 같다. 2. Code #include #include #include #include using namespace std; void cantor(int n) { int ..
https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 1. Logic 재귀를 이해하고 있다면 쉽게 풀 수 있는 문제이다. 각 노드의 부모 노드를 순서대로 출력해야 하기 때문에 부모 노드를 저장하는 배열(check)에 저장해줬다. 양방향으로 입력을 받았기 때문에 반복되는 계산을 막아주기 위해 vis배열도 추가해줬다. 수정 > 원래는 vis배열에 넣어줬지만 check배열을 -1로 초기화 시켜준 다음 -1이 아니면 continue하도록 설계해주면 100001개짜리 배열 하나를 덜 써도 된다 2. Code #includ..
https://www.acmicpc.net/problem/2056 2056번: 작업 수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다. 각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다. 몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해 www.acmicpc.net 1. Logic 처음에 이 문제를 딱 보고 위상정렬인줄 알았다. 하지만 위상정렬의 탈을 쓴 DP문제였고 결국 멘토한테 도움을 받았다. 내가 처음에 짠 코드는 동시에 진행하는 작업 중에 가장 시간이 오래 걸리는 작업의 시간이 고려되지 않을 수도 있는 코드였다. 그래서 이 문제는 위상정렬과 코드가 비슷하긴 하지만 DP로 풀이해야 한다. 2. Code #include using namespac..
