https://www.acmicpc.net/problem/16987 16987번: 계란으로 계란치기 원래 프로그래머의 기본 소양은 팔굽혀펴기를 단 한 개도 할 수 없는 것이라고 하지만 인범이는 3대 500을 넘기는 몇 안되는 프로그래머 중 한 명이다. 인범이는 BOJ에서 틀린 제출을 할 때마다 턱 www.acmicpc.net 1. Logic 조건 그대로 구현하면 된다. 구현이 약간 까다롭지만 계란의 수 N의 크기가 8로 엄청 작기 때문에 브루트포스로 풀이할 수 있다는 것을 유추할 수 있다. 구조체를 사용하지 않고 내구도와 무게를 따로 저장하는 배열을 선언하여 풀이했다. 2. Code #include #include using namespace std; int n; int dura[10]; int weig..
Algorithm
https://www.acmicpc.net/problem/1431 1431번: 시리얼 번호 첫째 줄에 기타의 개수 N이 주어진다. N은 50보다 작거나 같다. 둘째 줄부터 N개의 줄에 시리얼 번호가 하나씩 주어진다. 시리얼 번호의 길이는 최대 50이고, 알파벳 대문자 또는 숫자로만 이루어 www.acmicpc.net 1. Logic 각 조건에 따라 compare 함수를 커스텀해서 정렬하면 된다. 2. Code #include #include #include using namespace std; vector input; bool cmp(string a, string b) { //1번 조건 if(a.length() != b.length()) return a.length() < b.length(); //2번 ..
https://www.acmicpc.net/problem/11652 11652번: 카드 준규는 숫자 카드 N장을 가지고 있다. 숫자 카드에는 정수가 하나 적혀있는데, 적혀있는 수는 -262보다 크거나 같고, 262보다 작거나 같다. 준규가 가지고 있는 카드가 주어졌을 때, 가장 많이 가지 www.acmicpc.net 1. Logic map을 사용해서 풀었다. 2. Code #include #include using namespace std; map m; int main() { long long ans = 0; long long n; cin >> n; while(n--) { long long a; cin >> a; m[a]++; ans = max(ans, m[a]); } for(auto &a : m) { ..
https://www.acmicpc.net/problem/14503 14503번: 로봇 청소기 첫째 줄에 방의 크기 $N$과 $M$이 입력된다. $(3 \le N, M \le 50)$ 둘째 줄에 처음에 로봇 청소기가 있는 칸의 좌표 $(r, c)$와 처음에 로봇 청소기가 바라보는 방향 $d$가 입력된다. $d$가 $0$인 경우 북쪽 www.acmicpc.net 1. Logic 우와 구현은 역시 까다롭다. 문제를 보자마자 최단거리 알고리즘을 사용해야 할 것같아서 BFS를 사용하려고 했지만 문제와 맞지 않아 DFS가 더 적절하다고 판단했다. 이유는 계속 탐색이 아니라 한번 시작해서 한번 실패하면 바로 종료되기 때문에? 그리고 방향을 유지해야하기 때문에! 로직은 문제에 있는 그대로 실수하지 않고 구현하면 된다..
https://www.acmicpc.net/problem/15988 15988번: 1, 2, 3 더하기 3 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net 1. Logic 재귀로 들어가서 0이 되면 경우의 수 1을 count해준다. 다만 숫자가 크기 때문에 타입을 long long 으로 해줬다. 2. Code #include #include using namespace std; long long dp[1000001]; long long solve(long long n) { if(n == 0) return 1; else if(n < 0) return 0; long long &ret = dp[n]; if..
https://www.acmicpc.net/problem/5582 5582번: 공통 부분 문자열 두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오. 어떤 문자열 s의 부분 문자열 t란, s에 t가 연속으로 나타나는 것을 말한다. 예를 들 www.acmicpc.net 1. Logic LIS약간 변형? str1과 str2의 문자가 같으면 이전최대길이에 +1을 해준다! 2. Code #include using namespace std; int dp[4001][4001]; string str1, str2; int solve(int s1, int s2) { if(s1 == str1.size() || s2 == str2.size()) return 0; int..
https://www.acmicpc.net/problem/2157 2157번: 여행 첫째 줄에 N(1 ≤ N ≤ 300), M(2 ≤ M ≤ N), K(1 ≤ K ≤ 100,000)가 주어진다. K는 개설된 항공로의 개수이다. 다음 K개의 줄에는 각 항공로에 대한 정보를 나타내는 세 정수 a, b, c(1 ≤ a, b ≤ N, 1 ≤ c ≤ 1 www.acmicpc.net 1. Logic 동일한 경로의 비행기 노선이 있을 수 있기 때문에 기내식의 점수가 가장 높은 것 만을 입력받아줬다. 그리고 DP배열이 의미하는 바는 당연 가장 높은 기내식 점수이다. dp[도시의 번호][몇번째로 방문한 도시인지] 2. Code #include #include #include #include using namespace ..
https://www.acmicpc.net/problem/9657 9657번: 돌 게임 3 상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY을 출력한다. www.acmicpc.net 1. Logic 먼저 dp테이블의 의미는 dp[i] i개의 돌에서 턴을 잡은 사람의 승패 유무이다. 문제에서 1개, 3개, 4개를 가져갈 수 있다고 했고 항상 상근이가 먼저 시작한다고 했기 때문에 돌 갯수 | 우승자 1개 | 상근이 2개 | 창영이 3개 | 상근이 4개 | 상근이 항상 이렇게 이기고 이후는 이전에 메모이제이션 된 값으로 부분문제가 쪼개지기 때문에 DP로 풀 수 있다. 항상 두 사람이 완벽하게 게임을 한다고 했으며 항상 상근이가 먼저 시작하기 때문에 한번이라도 상근이가 이기는 경우가 생기면 해당 n개..
https://www.acmicpc.net/problem/2253 2253번: 점프 N(2 ≤ N ≤ 10,000)개의 돌들이 같은 간격으로 놓여 있다. 편의상 순서대로 1, 2, …, N번 돌이라고 부르자. 당신은 현재 1번 돌 위에 있는데, 이 돌들 사이에서 점프를 하면서 N번째 돌로 이동을 하려 www.acmicpc.net 1. Logic 1번째 돌에서 시작하여 n번째 돌까지 가야하지만 중간에 밟지 못하는 돌이 존재한다. 이런 돌을 걸러주기 위해 bool배열을 통해 체크해준다. 재귀를 통해 0까지 들어가며 부문문제를 해결해준다. 부분문제는 1. 이전에 이동했던 칸수와 동일하게 이동하는 경우 2. 이전에 이동했던 칸수-1칸 이동하는 경우 3. 이전에 이동했던 칸수+1 이동하는 경우 이렇게 3가지 이다..
https://www.acmicpc.net/problem/11653 1. Code #include using namespace std; int main() { int n; cin >> n; if (n == 1) return 0; for (int i = 2; i
