https://www.acmicpc.net/problem/11501 11501번: 주식 입력의 첫 줄에는 테스트케이스 수를 나타내는 자연수 T가 주어진다. 각 테스트케이스 별로 첫 줄에는 날의 수를 나타내는 자연수 N(2 ≤ N ≤ 1,000,000)이 주어지고, 둘째 줄에는 날 별 주가를 나타 www.acmicpc.net 1. Logic - 해당 문제는 주어진 배열을 앞에서 부터 풀이하게 될 경우 최댓값까지 배열을 돌고 또 최댓값을 구해서 배열을 돌아야해서 이중 for문을 사용하게 되어 시간복잡도가 O(n^2)이지만 뒤에서부터 풀이하게되면 다음값을 보고 최댓값인지 알 수 있기 때문에 O(n)으로 풀 수 있다. 최악의 경우를 생각 해 봤을 때 10000 *999999 곱하게되면 int 의 범위를 훨씬 넘..
Algorithm
https://www.acmicpc.net/problem/12852 12852번: 1로 만들기 2 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 자연수 N이 주어진다. www.acmicpc.net 1. Logic 1. 주어진 정수 X를 조건대로 검사하며 조건에 맞게 재귀함수에 넣어 계산 한 후 임시 변수 next에 담는다. 2. 다음에 나올 값이 현재의 dp에 담긴 값보다 작아야 연산을 최소로 하기 때문에 해당 next값과 현재 ret 즉 지금의 dp[num]값과 비교를 해서 next값이 더 작다면 dp와 나중에 path를 출력해줄 before 배열을 갱신시켜준다. 2. Code #include using namespace std; int n; const int INF = 987654321; i..
https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 1. Logic - 처음에 구현한 방식은 DP테이블을 세우고 재귀함수로 문제를 풀었었다. 동전의 sum 값과 얼마짜리 동전을 사용했는지를 표기하는 DP테이블을 구성했고 dp[10001][101]로 구성했다 이렇게 되면 n * k만 해도 4MB가 넘어가므로 당연하게도 메모리초과가 났다. 이 다음 생각한 방법으로는 상향식으로 흔히 점화식을 세워서 푸는 방법으로 풀었다. 항상 재귀로 풀으려고해서 점화식을..
https://www.acmicpc.net/problem/5557 5557번: 1학년 상근이가 1학년 때, 덧셈, 뺄셈을 매우 좋아했다. 상근이는 숫자가 줄 지어있는 것을 보기만 하면, 마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 사이에는 '+' 또는 '-'를 넣어 등식을 만들며 놀 www.acmicpc.net 1. Logic - 분기가 +, -로 이루어지기 때문에 2개의 재귀를 들어가야한다. - DP Tabel을 생성할때 처음 인자는 sum의 범위, 두번째 인자는 몇번째 인덱스를 돌고있는지 체크한다. 2. Code #include using namespace std; int n; vector vec; long long dp[30][101]; long long solve(int sum, int c..
https://www.acmicpc.net/problem/3085 3085번: 사탕 게임 예제 3의 경우 4번 행의 Y와 C를 바꾸면 사탕 네 개를 먹을 수 있다. www.acmicpc.net 1. Logic 1. 인접한 두 칸에 있는 사탕을 서로 바꿔야하기 때문에 swap함수를 사용해서 값을 변경해 준다. 2. 같은 색의 사탕을 먹어야 하기 때문에 현재칸과 그 다음칸을 비교하면서 진행하며 cnt를 올려준다. 3. 최댓값을 갱신해준다. 2. Code #include using namespace std; vector vec; int n; int calc() { // 가로 int ans = -92735; for(int i = 0; i < n; i++) { int cnt = 1; for(int j = 0; j..
https://www.acmicpc.net/problem/1065 1065번: 한수 어떤 양의 정수 X의 각 자리가 등차수열을 이룬다면, 그 수를 한수라고 한다. 등차수열은 연속된 두 개의 수의 차이가 일정한 수열을 말한다. N이 주어졌을 때, 1보다 크거나 같고, N보다 작거나 www.acmicpc.net 1. Logic 2가지 상황으로 분할해 볼 수 있다. 1. n이 99이하인 경우 2. n이 100이상인 경우 - 1 ~ 99까지의 수는 항상 등차수열을 이루기 때문에 99이하의 숫자가 나오게되면 즉시 숫자를 리턴한다! - 100이상의 숫자는 어짜피 999까지 비교하면 되기 때문에 3부분으로 나눠서 100자리 10자리 1자리 숫자를 각각 비교한다. 2. Code #include using namespa..
https://www.acmicpc.net/problem/2437 2437번: 저울 하나의 양팔 저울을 이용하여 물건의 무게를 측정하려고 한다. 이 저울의 양 팔의 끝에는 물건이나 추를 올려놓는 접시가 달려 있고, 양팔의 길이는 같다. 또한, 저울의 한쪽에는 저울추들만 놓 www.acmicpc.net 1. Logic - 받은 숫자를 오름차순으로 정렬한다. 처음 숫자부터 더해가며 sum > vec[i] 일 경우 수를 조합하여 구할 수 있고 sum > n; for..
https://www.acmicpc.net/problem/10448] 10448번: 유레카 이론 프로그램은 표준입력을 사용한다. 테스트케이스의 개수는 입력의 첫 번째 줄에 주어진다. 각 테스트케이스는 한 줄에 자연수 K (3 ≤ K ≤ 1,000)가 하나씩 포함되어있는 T개의 라인으로 구성되어 www.acmicpc.net 1. Logic - 세 합이 100을 넘는 경우는 n이 45인경우부터 1000을 넘기 때문에 45까지 for문을 돌며 합을 계산해 놓는다. - 계산하고 싶은 삼각수를 받은 후 3중 for문을 돌며 찾게되면 값을 반환한다 2. Code #include using namespace std; int triangleNum[1001]; bool FindTri(int n) { for(int i =..
https://www.acmicpc.net/problem/2309 2309번: 일곱 난쟁이 아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다. www.acmicpc.net 1. Logic 1. 난쟁이들의 키의 총 합이 100이고 난쟁이들의 수가 정해져있기 때문에 키를 입력받으면서 동시에 전부 더해준다 2. 2명을 제외하면 되기 때문에 2중 for문을 돌면서 2명의 키를 뺀것이 100이 되면 출력해준다. 2. Code #include using namespace std; vector vec; int main() { int sum = 0; for(int i = 0; i < 9;..
https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 1. Logic - 딱 봐도 BFS지만 나눠야 하는 부분이 3가지이다. 1. 조건을 같지 않을때로 걸고 BFS를 돈다 2. 이후 배열을 순회하며 R 또는 G중 원하는 것을 선택하여 R > G / G > R로 변경해준다. 3. 다시 BFS를 돈다. 2. Code #include using namespace std; int n; vector vec(101, ""); vector vis(101,..
