https://www.acmicpc.net/problem/2776 2776번: 암기왕 연종이는 엄청난 기억력을 가지고 있다. 그래서 하루 동안 본 정수들을 모두 기억 할 수 있다. 하지만 이를 믿을 수 없는 동규는 그의 기억력을 시험해 보기로 한다. 동규는 연종을 따라 다니며, www.acmicpc.net 1. Logic 이 문제는 unordered_map을 활용한 풀이, 이분탐색을 활용한 풀이 총 두가지 방법으로 풀이 가능하다. 2. Code 해시 맵 풀이 #include #include using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); int t; cin >> t; while(t--) ..
백준
https://www.acmicpc.net/problem/17266 17266번: 어두운 굴다리 인하대학교 후문 뒤쪽에는 어두운 굴다리가 있다. 겁쟁이 상빈이는 길이 조금이라도 어둡다면 가지 않는다. 따라서 굴다리로 가면 최단거리로 집까지 갈수 있지만, 굴다리는 어둡기 때문에 빙 www.acmicpc.net 1. Logic 값이 참이 되는 구간을 살펴보면 정답 mid를 기준으로 0~left까지는 false, right~n까지는 true이다. 여기서는 참이 되는 값중 최솟값을 구해야 하기 때문에 right를 반환해 주면 된다. 2. Code #include #include using namespace std; int n, m; vector input; int binarySearch() { int start..
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번에 있는 ..
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 ..
