iridescent

https://www.acmicpc.net/problem/1890

[규칙]

1. 오른쪽과 아래쪽만 이동 가능
2. 칸에 적혀져 있는 칸만큼 이동
3. 0이 나오면 못 감
4. 경로의 개수는 2^63-1보다 작거나 같음
5. 경로의 개수 구해라

[실패 원인]

1. 문제를 제대로 안 읽었다. (최단기 거리인 줄,, )
2. 제일 간단한 DFS로 푸니깐 시간 초과가 났다.
3. 경로의 개수가 2^63-1보다 작거나 같다 == int형으로는 안된다. 

[풀이 설명]

DFS로 푼 것이랑 원리는 비슷한데

반복문을 통해 풀었다. 

• 따른 배열을 만들어서
• route [0][0] 배열에는 1을 저장한다. 
• 각 행열을 다 지나치면서
  • 0이 아니거나, 배열 만든 것(route)이 0이 아니면
  • 가로, 세로에 각 칸에 있는 칸만큼 더해서 더한다. 

이렇게 경로를 저장할 수 있다. 

[소스코드]

#include<iostream>
using namespace std;

int N;
int input_array[101][101];
long long route[101][101] = { 0 };

int main() {
	cin >> N;
	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
			cin >> input_array[i][j];
	
	route[0][0] = 1;
	for(int row = 0; row<N; row++)
		for (int col = 0; col < N; col++) {
			if (input_array[row][col] != 0 && route[row][col]!= 0) {
				if (row + input_array[row][col] < N)
					route[row + input_array[row][col]][col] += route[row][col];
				if (col + input_array[row][col] < N)
					route[row][col + input_array[row][col]] += route[row][col];
			}
		}
	cout << route[N-1][N-1];
	return 0;
}

https://www.acmicpc.net/problem/11055

[규칙]

1. 증가 부분 수열
2. 합이 가장 큰 것

[실패 원인]

1. 알고리즘은 간단하였는데, 비교하는 부분에서 합이 큰 값이랑 비교를 안 하고 자신과 작은 값의 수열과 비교해서 틀렸다.

[풀이 설명]

• 증가하면서 합이 가장 큰 것을 선택하면 된다. 
• 나는 배열을 따로 만들어서, 각자 증가하는 부분에 있어서 합을 각 행마다 저장을 했다. 
• 이게 무슨 말이라면, 
•  

  

자신보다 작은 값의 최댓값과 자신을 더하면 된다고 생각했다. 

ex) 50은 자신보다 작은 값이 1과 2가 있다. 

그치만 2는 1을 이미 더한 값이기 때문에 2의 값만 더해주면 된다. (연한 주황색 화살표 참조)

[소스코드]

#include<iostream>
#include <vector>
#include<algorithm>
using namespace std;

int main() {
	int N, output_max_num = 0;

	cin >> N;
	vector<int> input_A(N + 1), add_array(N+1,0);
	
	for (int i = 0; i < N; i++)
		cin >> input_A[i];

	for (int i = 0, max_add_num; i < N; i++) {
		max_add_num = 0;
		for (int j = 0; j < i; j++) {
			if (input_A[i] > input_A[j])
				max_add_num = max(max_add_num, add_array[j]);
		}
		add_array[i] = input_A[i] + max_add_num;
		output_max_num = max(output_max_num, add_array[i]);
	}
	cout << output_max_num;
	
	return 0;
}

https://www.acmicpc.net/problem/22857

[규칙]

1. 수열에서 K번 삭제 가능
2. 삭제 후 짝수로 이루어져 있는 연속한 부분 수열 
3. 연속한 부분 수열

[실패 원인]

1. 부분 수열에 대해 내가 잘 몰랐다. 
   • array = [1,2,3,4,5,6,7]
     • 연속된 부분 수열 : {1}, {2}, {3}, {4], {5} ,.... {1,2}, {2,3},.... {1,2,3,4},....

[풀이 설명]

• 최대한 포인터를 사용하지 않고 해 보았다. 
• 어차피 연속된 부분 수열이기 때문에, 짝수부터 시작해야 한다고 생각했다.
  1. 짝수 시작 점부터 짝수 개수를 센다.
  2. 홀수가 나오면 홀수 개수를 센다 (세고 있던 짝수 수는 초기화한다.)
  3. 배열에 짝수, 홀수 수를 각각 넣는다. 
• 홀수의 개수가 들어있는 배열을 이용한다.
  1. 홀수의 개수가 들어있는 배열 0번째부터 더해서 K가 넘을 때까지 반복한다.
     • 반복하면서 짝수의 개수를 더한다.

간단하게 적었지만, 설명이 제대로 안 된 것 같아 그림을 그려서 설명해보자면

위의 그림처럼 노란색 밑줄은 짝수, 초록색 밑줄은 홀수이다.

짝수와 홀수가 연속된 부분을 개수를 세어 각각 배열에 넣은 모습이다. 

문제에서 원소를 K번 삭제하기 때문에 odd의 수가 K번 보다 작어야 한다. 

• 예를 들면 k가 2라면
  • odd배열에서 2보다 작거나 같게 반복하면서
  • even배열을 더해준다.
  • 그렇게 되면 2 + 3으로 젤 긴 수열은 5가 된다. 

• 다른 예시를 들어보면

K = 5 일 때,

odd가 2와 3을 선택을 해야

젤 큰 길이를 가지는 4 + 6 +5가 된다. 

[코드]

#include <iostream>
#include<vector>
#include<algorithm>
using namespace std;

int main() {
	int N, K;
	int odd_row = 0;
	cin >> N >> K;
	vector<int> even(N+1), odd(N+1);
	
    //odd, even배열에 넣기
	for (int i = 0,num, even_start =0,even_row = 0; i < N; i++) {
		cin >> num;
		if (even_start == 0 && num % 2 == 0)even_start = 1;
		if (even_start == 1) {
			if (num % 2 == 0) {
				even[even_row] += 1;
				if(odd[odd_row] > 0)odd_row++;
			}
			else {
				odd[odd_row] += 1;
				if (even[even_row] > 0)even_row++;
			}
		}
	}
    
    //최댓값 구하기
	int max_sum = 0;
	for (int i = 0, sum; i <= odd_row; i++) {
		sum = 0;
		for (int j = i, count = 0;  j <= odd_row; j++) {
			count += odd[j];
			if (count <= K)	sum += even[j];
			else { 
				sum += even[j]; 
				break; 
			}
		}
		max_sum = max(max_sum, sum);
	}
	cout << max_sum;
	return 0;
}

https://www.acmicpc.net/problem/1932

[규칙]

1. 맨 위의 층부터 시작

2. 아래의 있는 수 중 최대가 되는 경로 찾기

3. 대각선 왼쪽 또는 오른쪽에 있는 것만 선택 가능

4. 삼각형 크기 500이하

5. 시간제한 2초

[실패 원인]

• 이것도 마찬가지로 마음 편하게 DFS로 풀었더니 시간 초과가 났다. 
  
  • 시간이 2초나 되는데 오류가 난 것이다. ㅋㅎㅋㅎ, 세상에,,,
  • 그래서 백준의 '질문 검색'버튼을 이용해서 다른 분들도 시간 초과가 났나 보았다. 
  • 보니깐 문제가 '메모이제이션(Memoization) 을 이용해야 한다고 한다. 
    • 메모이제이션이란?
      • 구글에 검색해서 보았더니, 이전에 계산한 값을 메모리에 저장하여 중복적인 계산을 제거하는 것이라고 한다. 
      • 참고 : https://wondytyahng.tistory.com/entry/memoization-%EB%A9%94%EB%AA%A8%EC%9D%B4%EC%A0%9C%EC%9D%B4%EC%85%98
      • 근데 이걸 보고 이걸 저장할 값이 있나 생각을 해보았다. 
      • 그전에, 이걸 DFS를 사용할 필요가 있나?라는 생각을 해보니 답이 나왔다. 

[풀이 설명]

• 먼저 마지막 행 위의 행부터 시작하기로 했다. 

  • 

    n-2행부터
    • 자기 아래의 값, 아래 +1 값 중 큰 값을 자신과 더했다. 
    • 옆에 그림을 보면 알 수 있다. 
    • 첫 번째를 설명해보면, 젤 마지막 행에서 4와 5중에서는 5가 크므로, 2(자기 자신)과 5를 더해준다. 
    • 이렇게 0번째 행까지 해준다. 

[소스 코드]

#include <iostream>
#include<algorithm>
using namespace std;

int main() {
	int n; //삼각형의 크기 
	int Triangle[501][501];
	int max_num = 0;
	cin >> n;
	for (int i = 0; i < n; i++)
		for (int j = 0; j <= i; j++)
			cin >> Triangle[i][j];

	for (int row = n - 2; row >= 0; row--)
		for (int col = 0; col <= row; col++)
			Triangle[row][col] += max(Triangle[row + 1][col], Triangle[row + 1][col + 1]);

	cout << Triangle[0][0];

	return 0;
}

https://www.acmicpc.net/problem/2579

[규칙]

1. 계단은 한 번에 한 칸 or 두 칸

2. 연속 세 칸  X

3. 마지막 도착 계단은 반드시 밟아야 함

4. 총 점수의 최댓값 구하기

[실패 원인]

1. DFS로 푸는 게 젤 안전할 것 같아서 풀었는데 시간 초과가 나왔다. 

- 아마 제한시간이 1초여서 계단의 수가 300 이하이지만, 시간이 부족한 것 같았다. 

2. DFS 말고 아래 설명할 알고리즘으로 풀었는데, 세번째 칸이 무조건 (첫 번째 계단 + 세 번째 계단) 값인 줄 알았는데 문제를 잘 보니 

이렇게 시작점은 포함되지 않기 때문에,(첫 번째 계단 + 세 번째 계단) OR(두 번째 계단 최댓값 + 세 번째 계단)의 최댓값이 세 번째 계단 값이었다. 

[풀이 설명]

DFS가 실패한 뒤, 실패한 이유는 시간 초과여서 '그럼 반복하여 배열을 이용해서 해보자'라는 생각을 하게 되었다. 

순서대로 생각을 해보면, 

º 첫 번째 계단은 1번째 계단 값

º 두 번째 계단은 1번째 계단 + 2번째 계단

º 세 번째 계단은

    (1번째 계단 + 3번째 계단) 

            OR

    (1번째 계단 + 2번째 계단+ 3번째 계단) : 시작점은 연속된 세 개의 계단을 밟아서는 안된다는 조건에 빠지기 때문

º 네 번째 계단은

    (1번째 계단 + 3번째 계단 + 4번째 계단) 

            OR

    (1번째 계단 + 2번째 계단+ 4번째 계단)

º 다섯 번째 계단은

    (2번째 계단 + 4번째 계단 + 5번째 계단) 

            OR

    (3번째 계단+ 5번째 계단) 

이렇게 된다.

그래서 식을 생각해보면

X자리의 최댓값을 구하려면

X자리 계단 값 + X-2의 최댓값

X자리 계단 값 + X-1의 계단 값 + X-3의 최댓값

이라는 식이 나온다.

그렇지만 X-1은 왜 계단 값을 구하냐

이것은 옆의 판을 보면 알 수 있다. 

5번의 계단의 최댓값을 구할 시

2번, 4번, 5번 이렇게 뛰어넘는다고 생각하면

4번째 계단은 무조건 앞에 3번을 포함하지 않아야 한다. 

4번째 계단의 최댓값을 구한다면, 3번이 포함할 수 있기 때문에 사용하지 않는다. 

이렇게 소스코드를 짜면,

#include <iostream>
#include<algorithm>
using namespace std;


int main() {
	int N;
	int score[301];
	int max_score[301];

	cin >> N;
	for (int i = 0; i < N; i++)
		cin >> score[i + 1];

	max_score[1] = score[1];
	max_score[2] = score[1] + score[2];
	max_score[3] = max(score[2]+score[3],score[1] + score[3]);

	for (int i = 4; i <= N; i++) {
		max_score[i] = max(score[i] + max_score[i - 2], max_score[i - 3] + score[i - 1] + score[i]);
	}
	cout << max_score[N];
	return 0;
}

나온다. 

https://www.acmicpc.net/problem/20300

이 문제는 정말 간단하다. 

음 먼저 최솟값을 구해야하기 때문에 

작은 것 끼리 더하는게 아닌, 

어릴 적 덧셈 빨리 하는 법 하면 기억나는 

첫번째 자리랑 끝자리 더해서 n/2만큼 반복하면 합이 나온다는 방법을 이용했다 

(방법 이름이 생각 안 난다. )

어쨋든 

알고리즘

• 개수를 입력받는다. 
• 개수만큼 숫자를 받고
• 정렬한다. 
• 받은 개수가 짝수이면
  • 앞자리 , 끝자리 더한다
  • 앞자리 ++, 끝자리 ++ n/2번 더한다. 
• 받은 개수가 홀수이면
  • 끝자리 max_num으로 넣고
  • 짝수와 같이 진행한다. 

여기서 add_num을 다르게 한 이유가. 

홀수는 끝자리를 먼저 더해서 -2를 한 것이고, 

짝수는 끝자리 배열 인덱스를 접근하기 위해서다.

코드는 

#include <iostream>
#include<vector>
#include <algorithm>
using namespace std;

int main() {

	int testcase;
	cin >> testcase;
	vector<long long> input;
	long long output_max = 0;
	long long num;
	for (int i = 0; i < testcase; i++) {
		cin >> num;
		input.push_back(num);
	}

	sort(input.begin(), input.end());
	int add_num = 1;
	if (testcase % 2 == 1) {
		output_max = max(output_max, input[testcase - 1]);
		add_num = 2;
	}
	for (int i = 0, end = testcase - add_num; i < testcase / 2; i++,end--) {
		output_max = max(output_max, input[i] + input[end]);
	}
	cout << output_max;
	return 0;
}

https://www.acmicpc.net/problem/1758

이건 그냥 계산만 하는 거라서
왜 그리디 알고리즘인지 모르겠다.

나중에 여쭤봐야지

그냥 간단하게, 팁을 많이 준 사람은 앞에 순서에 해서
많이 받게 하는 것이다.

여기서 오래 걸린 이유는,
python의 입출력을 어떻게 해야할지 몰라서다.

처음에 입출력을 input()으로만 사용해서 했더니
틀렸다는 것이다.

진짜 왜 틀렸을까. 했는데
입출력 문제였다.

그래서 input()대신
sys.stdin.readline을 사용하려는데
그것도 jupyter Notebook에서 invalid literal for int() with base 10: '' 이렇게 나온것이다.
int(sys.stdin.readline)을 사용했는데,,,

파이참으르 사용해서 확인했더니 잘 되기만 했다. ㅋㅎ
그냥 주피터가 잘 못한듯,,,;;

새로운 것을 배웠다,
input()보단
sys.stdin.readline()이 더 빠르다는 것을,
그리고 여러 개 받을 땐 (정수형)
int(sys.stdin.readline()) for _ in range(n)을 사용하자!

import sys input = sys.stdin.readline testcase = int(input()) input_num = [int(input()) for _ in range(testcase)] input_num.sort(reverse= True) sum_output = 0 for i in range(testcase): if input_num[i] - i >0: sum_output += input_num[i]-i print(sum_output)

https://www.acmicpc.net/problem/1541

처음에 왜 55-50+40이 -35가 나오는지 몰랐다. 

그런데 식을 보니깐

마이너스가 나오려면 마이너스가 커야 하기 때문에 

55-(50+40)하면 -35가 나온다는 걸 깨달았다. 

수업시간에 깨달아서 좀 진정하고 코드를 짰다. 

역시 알고리즘 먼저 생각하고 짜니깐.

짜는건 오래 안 걸린다...

알고리즘

• 입력을 받는다
• stringstream으로 숫자 파싱한다. 
• 파싱한 숫자가 0보다 크다면(양수)
  • sum(마이너스 일 때 더한 수)가 0이면 push
  • sum이 0이 아니라면, 
    • 앞에 마이너스가 있어서 마이너스 할 것을 더하고 있다면 sum더하기 ( ex, -20+30일 경우)
    • 그냥 양수가 나온 것이라면, push (ex, +50+60+70)
• 0보다 작다면(음수)
  • 마이너스가 나온 것이 처음 or 마이너스 시작이면
    • check true로 하고(시작했다는 것을 알림)
    • sum에 num 더하기
  • 앞에 마이너스가 있어서 더하고 있었는데 다음 마이너스가 나온 것이라면 (ex, -20 +30 40 -30)
    • 더한 값 전부 -1곱해서 push
    • sum을 새로 업데이트 

그냥 생각하면 쉬웠는데,,

조금 더러운 코드가 된게 아닌가 싶다...

#include <iostream>
#include<sstream>
#include<string>
#include <stack>

using namespace std;
int main() {
	stringstream ss;
	string input;
	stack<int> number;

	int num;
	int sum = 0;
	cin >> input;
	ss.str(input);
	bool check = false;
	while (ss >> num) {
		if (num > 0) {
			if (sum == 0) {
				number.push(num);
			}
			else {
				if (!check) {
					number.push(num);
				}
				else {
					sum += num;
				}
			}
		}
		else {
			if (!check) {
				check = true;
				sum += num * (-1);
			}
			else {
				number.push((-1)*(sum));
				sum = num * (-1);
				check = true;
			}	
		}
	}
	if(check)
		number.push((-1)*(sum));
	int output = 0;
	for (int i = 0; !number.empty(); i++) {
		output += number.top();
		number.pop();
	}
	cout << output;
	return 0;
}