코딩무식자 전공생

문제출처: https://www.acmicpc.net/problem/1912

문제

n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다.

예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다.

입력

첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.

출력

첫째 줄에 답을 출력한다.

풀이

문제의 정답률이 사람들이 얼마나 dp를 어려워하는지를 보여주네요..하지만 정답을 도출하는 과정이 어렵진않습니다. 헷갈릴 순있어도.....

dp[N]은 첫번째 수~N번쨰 수까지의 수 중 연속된 최댓값을 저장합니다. 그렇기 때문에  혹시라도 dp[2],dp[3],d[4]을 10이라고 생각 하셨던 분들은 접근을 잘못 한겁니다.

결과적으로 dp[2]는 10-4=6, dp[3]=9..이런식이므로 이어지므로 dp[i]=max(dp[i-1]+arr[i],arr[i])만 해주시면됩니다. 여태까지의 최대연속합dp[N]이 arr[N]보다 작을 때 arr[N]이 최대값이 된다는것만 주의하면됩니다.(이 때 arr[N]은 0개연속). 그리고 연산하면서 정답을 출력할 변수를 매번 최대값으로 갱신해주면됩니다. 주의: dp[n]은 정답아님(32)

코드

#include<iostream>
#include<algorithm>
using namespace std;
int arr[100001];
int dp[100001];
//index까지 최대합 저장 dp[5]=1~5번째 수 중 최대연속값

int main()
{
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> arr[i];
	dp[1] = arr[1];
	int MAX = dp[1];
	//10,-4 .. 일때 dp[2]=10이아님....6임
	//dp[2]=10은 연속하지않음,그러나 10,16일때
	//dp[2]는 16일때 가장 큰 수(0개연속)
	for (int i = 2; i <= n; i++)
	{
		dp[i] = max(arr[i], dp[i - 1] + arr[i]);
		//cout << dp[i] << " ";
		if (dp[i] > MAX)MAX = dp[i];
	}
	cout << MAX << endl;
}

결과

문제출처: https://www.acmicpc.net/problem/2193

문제

0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다.

1. 이친수는 0으로 시작하지 않는다.
2. 이친수에서는 1이 두 번 연속으로 나타나지 않는다. 즉, 11을 부분 문자열로 갖지 않는다.

예를 들면 1, 10, 100, 101, 1000, 1001 등이 이친수가 된다. 하지만 0010101이나 101101은 각각 1, 2번 규칙에 위배되므로 이친수가 아니다.

N(1 ≤ N ≤ 90)이 주어졌을 때, N자리 이친수의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다.

출력

첫째 줄에 N자리 이친수의 개수를 출력한다.

풀이

dp문제는 규칙을 찾는게 중요합니다. 조건에맞게 규칙을 하나씩 찾아보면 분명 쉽게 답이 나오는 문제도많습니다.

일단 1~90자리의 이친수의 개수를 담을 dp[91]배열을 선언합니다.(dp[5]=5자리 이진수의 이친수갯수 저장)

규칙을 찾아봅시다.(노트에 적어가며) 

1자리이친수: 1(1),  2자리: 1(10),  3자리:2(100,101),  4자리:3(1000,1010,1001).......규칙이보이시나요?

2번쨰 인덱스부터 dp[i]=dp[i-2]+dp[i-1]이성립합니다.! (규칙이 안보이시면 5,6자리까지구해보세요)

주의할건 배열을 int형선언이아닌, long long형으로 선언해야한다는겁니다. 입력값이 최대 90자리이므로,, int형범위로는 택도없습니다. 참고: long long 형범위: -9,223,372,036,854,775,808 ~ 9,223,372,036,854,775,807

코드

#include<iostream>
using namespace std;
long long dp[91];
//1~90자리의 수의 이친수의 개수담는배열

int main()
{
	int n;
	cin >> n;
	dp[1] = 1, dp[2] = 1;
	/*dp[3] = 2, dp[4] = 3;
	dp[5] = 5, dp[6] = 8;*/
	for (int i = 3; i <= n; i++)
		dp[i] = dp[i - 2] + dp[i - 1];
	cout << dp[n] << endl;
}

문제출처: https://www.acmicpc.net/problem/1822

   문제

//#include<iostream>
//#include<set>
//using namespace std;
//int main()
//{
//	int a, b;
//	cin >> a >> b;
//	set<int>s;
//	set<int>::iterator it;
//	int x;
//	for (int i = 0; i < a; i++)
//	{
//		cin >> x;
//		s.insert(x);
//	}
//	for (int i = 0; i < b; i++)
//	{
//		cin >> x;
//		it = s.find(x);
//		if (it == s.end())
//			continue;
//		else
//			s.erase(x);
//	}
//	cout << s.size() << endl;
//	for (it = s.begin(); it != s.end(); it++)
//		cout<< *it<<" ";
//	cout << endl;
//}

#include<iostream>
#include<vector>
using namespace std;
int a[500001], b[500001], sorted[500001];
void merge(int a[], int start, int end);
void merge_sort(int a[], int start, int middle, int end);
int main()
{
	int n,m;
	cin >> n >> m;
	for (int i = 0; i < n; i++)
		cin >> a[i];
	for (int i = 0; i < m; i++)
		cin >> b[i];
	merge(a, 0, n - 1);
	merge(b, 0, m - 1);
	vector<int>v;
	int a_start = 0;
	int b_start = 0;
	while (a_start < n && b_start < m)
	{
		if (a[a_start] < b[b_start])
		{
			v.push_back(a[a_start]);
			a_start++;
		}
		else if (a[a_start] > b[b_start])
			b_start++;
		else
		{
			a_start++, b_start++;
		}
	}
	if (a_start < n)
	{
		for (int i = a_start; i < n; i++)
			v.push_back(a[i]);
	}
	cout << v.size() << endl;
	for (int i = 0; i < v.size(); i++)
		cout << v[i] << " ";
	cout << endl;

}
void merge(int a[], int start, int end)
{
	if (start < end)
	{
		int middle = (start + end) / 2;
		merge(a, start, middle);
		merge(a, middle + 1, end);
		merge_sort(a, start, middle, end);
	}
}
void merge_sort(int a[], int start, int middle, int end)
{
	int i = start;
	int j = middle + 1;
	int k = start;
	while (i <= middle && j <= end)
	{
		if (a[i] <= a[j])
			sorted[k++] = a[i++];
		else sorted[k++] = a[j++];
	}
	if (i > middle)
	{
		for (int l = j; l <= end; l++)
			sorted[k++] = a[l];
	}
	else
		for (int l = i; l <= middle; l++)
			sorted[k++] = a[l];
	for (int l = start; l <= end; l++)
		a[l] = sorted[l];
}

문제출처: https://www.acmicpc.net/problem/9366

문제

꿍은 오늘 학교에서 삼각형에 대해 배웠다. 삼각형은 변의 길이에 따라 다음과 같이 분류될 수 있다.

• 정삼각형(equilateral triangle)은 모든 변의 길이가 같다. 각 역시 60도로 모두 같다.
• 이등변삼각형(isosceles triangle)은 두 개의 변의 길이가 같다. 각 역시 두 개의 각의 크기가 같다.
• 부등변삼각형(scalene triangle)은 모든 변의 길이가 같지 않다. 각 역시 모두 다르다. 몇몇 부등변삼각형의 경우 직각삼각형이다.

수학선생님이 삼각형의 세 변의 길이를 가지고 삼각형을 분류하라는 숙제를 내줬는데 꿍은 정말 놀고싶다. 꿍이 놀수있도록 여러분이 도와주어라.

입력

입력의 첫 줄에는 테스트케이스의 개수 T(1 <= T <= 100)가 주어진다. 다음 T줄에는 각 줄에 삼각형의 세 변을 나타내는 3개의 정수 A,B,C(1 <= A,B,C <= 1,000,000)가 주어진다.

출력

각 테스트 케이스에 대해 삼각형이 “equilateral”, “isosceles”, “scalene” 타입 중 어느 타입에 속하는지 출력한다. 만약 주어진 세 변의 길이로 삼각형이 만들어지지 않을경우, “invalid!”를 출력한다.

풀이

정답률이 51프로 밖에안되는것은 주어진 삼각형의 종류에대해서만 생각했기때문이라고 생각합니다.

기본적으로 삼각형의 조건은 a<=b<c일때 a+b>c입니다. 역으로 a+b<=c일 때 삼각형은 성립불가합니다.

삼각형의 조건을 만족시키지 않을 때만 invalid를 출력하고 이어서 조건의 삼각형들에 대해 else,if로 분기시키면됩니다.

if 정삼각형일때, else if 이등변삼각형일때, else if 부등변삼각형일 때 else "invalid" 이런식으로 작성하면 오류가뜹니다. (else는 무조건 삼각형이 아닐때만.)

*부등변삼각형: 정삼각형, 이등변삼각형도 아닌 삼각형

코드

#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
	int t;
	cin >> t;
	int a[3];
	for(int i=1;i<=t;i++)
	{
		cin >> a[0] >> a[1] >> a[2];
		sort(a, a + 3);
		cout << "Case #" << i << ": ";
		if (a[0] + a[1] <= a[2])cout << "invalid!";
		else if (a[0] == a[1] && a[1] == a[2])
			cout << "equilateral";
		else if (a[0] == a[1] || a[1] == a[2] || a[0] == a[2])
			cout << "isosceles";
		else cout << "scalene";
		cout << endl;
	}
}

결과

문제출처: https://www.acmicpc.net/problem/1748

문제

1부터 N까지의 수를 이어서 쓰면 다음과 같이 새로운 하나의 수를 얻을 수 있다.

1234567891011121314151617181920212223...

이렇게 만들어진 새로운 수는 몇 자리 수일까? 이 수의 자릿수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N(1≤N≤100,000,000)이 주어진다.

출력

첫째 줄에 새로운 수의 자릿수를 출력한다.

풀이

노트에 규칙성을 찾기위해 각 자릿수의 수들의합은 몇자리인지 적어봅니다

(1~9는 9, 10~99는 180,100~999는 2700입니다. 보기의 120의 답은 252입니다. 규칙성을 눈치채셨나요?

답은 n-1자리수까지의 숫자들을 나열한 수의 자릿수 + (n(끝값) - n자릿수의 시작 수- +1) * n입니다.

( 120-> 9(1~9) +180(10~99) + 63(100~120)=252 )

좀 복잡해보이지만 코드를 보면 이해가 갈거에요.

결론적으로, 위의 수식에서 색칠된 부분만 변수로 선언하여 답을 유도하면됩니다.

코드

#include<iostream>
#include<string>
using namespace std;
int main()
{
	string n;
	cin >> n;
	//120의 자릿수=3
	int len = n.size();
	//1~9자릿수 합=9
	//10~99자릿수 합180
	//100~120자릿수 합 63
	//답: len-1자릿수까지의합+(n-n자리숫자의시작수+1)*n의 자릿수
	if (len == 1)
	{
		cout << stoi(n);
		return 0;
	}
	//temp1=n자리숫자일때끝값(1자리:9,2자리:99,3자리:999)
	//temp2=n자리숫자일때첫값(1자리:1,2자리:10,3자리:100)
	int ans = 0, temp1 = 9, temp2 = 1;
	for (int i = 1; i < len; i++)
	{
		ans += temp1 * i;
		temp1 *= 10;
		temp2 *= 10;
	}
	cout << ans + (stoi(n) - temp2 + 1) * len << endl;

}

결과

방향그래프가 주어질 때(일방 통행이므로!) 0번에서 99번노드로 가는 길이 있는지 탐색하는 문제입니다.

단순히 길이 있는지없는지만 파악하면되므로 0번노드부터 전체탐색을하여 dfs함수의 매개변수v가 99이면 99번 노드까지 탐색을

한 것이므로 그 때 길이있다고 check하여 빠져나와 출력하면됩니다. 테스트케이스가 끝날 때마다 선언 해둔 배열만 초기화해주면됩니다.

자료구조책의 dfs개념파트를 보고 충분히 풀 수 있는 문제입니다.

코드

#include<iostream>
#include<cstring>
using namespace std;
int visited[100];
int graph[100][100];
void dfs(int v);
bool check;
int main()
{
	int t, v1, v2, edge;
	for (int i = 0; i < 10; i++)
	{
		memset(visited, 0, sizeof(visited));
		memset(graph, 0, sizeof(graph));
		check = false;
		cin >> t >> edge;
		for (int i = 0; i < edge; i++)
		{
			cin >> v1 >> v2;
			graph[v1][v2] = 1;
		}
		dfs(0);
		cout << "#" << t << " ";
		if (check)
			cout << 1;
		else
			cout << 0;
		cout << endl;
	}
}
void dfs(int v)
{
	visited[v] = 1;
	//99번쨰에 도달했으므로 길이 있는것임.
	if (v == 99)
	{
		check = true;
		return;
	}
	for (int i = 0; i < 100; i++)
	{
		if (!visited[i] && graph[v][i])
			dfs(i);
	}
}

전형적인 스택 문제입니다. 이런 유형의 문제들은 자료구조책의 스택단원을 공부하면서 한번쯤은 구현해봤을 문제입니다.

코드가 길어질까봐 stl로 작성했는데 스택을 처음 공부하시는분들은 복습겸 꼭 c언어 스타일로 구현해볼것을 권장합니다.

코드

#include<iostream>
#include<stack>
#include<string>
using namespace std;
int main()
{
	for (int t = 1; t <= 10; t++)
	{
		int len;
		cin >> len;
		stack<char>s;
		bool check = true;
		for (int i = 0; i < len; i++)
		{
			char c;
			cin >> c;
			switch (c)
			{
			case '[':
			case '{':
			case '<':
			case '(':
				s.push(c);
				break;
			case ']':
			case '}':
			case ')':
			case '>':
				if (s.empty())
				{
					check = false;
					break;
				}
				char pop = s.top();
				s.pop();
				if ((pop == '(' && c != ')') || (pop == '[' && c != ']') || (pop == '{' && c != '}') || (pop == '<' && c != '>'))
				{
					check = false;
					break;
				}
			}
		}
		cout << "#" << t << " ";
		if ((!s.empty() || check == false))
			cout << 0;
		else cout << 1;
			cout << endl;




	}

}