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

2차원 평면 위의 점 N개가 주어진다. 좌표를 y좌표가 증가하는 순으로, y좌표가 같으면 x좌표가 증가하는 순서로 정렬한 다음 출력하는 프로그램을 작성하시오.

첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다.

첫째 줄부터 N개의 줄에 점을 정렬한 결과를 출력한다.

a.y != b.y ? a.y < b.y : a.x < b.x;

#include <iostream>
#include <algorithm>

using namespace std;

struct cood {
    int x, y;
};

cood arr[100001] = {0, };

bool compare (cood a, cood b) {
    return a.y != b.y ? a.y < b.y : a.x < b.x;
}

int main()
{
    int n;
    cin >> n;
    
    for(int i = 0; i < n; ++i) scanf("%d %d", &arr[i].x, &arr[i].y);
    
    sort(arr,  arr + n, compare);
    
    for(int i = 0; i < n; ++i) printf("%d %d\n", arr[i].x, arr[i].y);\
    
    return 0;
}

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

2차원 평면 위의 점 N개가 주어진다. 좌표를 x좌표가 증가하는 순으로, x좌표가 같으면 y좌표가 증가하는 순서로 정렬한 다음 출력하는 프로그램을 작성하시오.

첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다.

첫째 줄부터 N개의 줄에 점을 정렬한 결과를 출력한다.

#include <iostream>
#include <algorithm>

using namespace std;

struct cood {
    int x, y;
};

cood arr[100001] = {0, };

bool compare (cood a, cood b) {
    return a.x != b.x ? a.x < b.x : a.y < b.y;
}

int main()
{
    int n;
    cin >> n;
    
    for(int i = 0; i < n; ++i) scanf("%d %d", &arr[i].x, &arr[i].y);
    
    sort(arr,  arr + n, compare);
    
    for(int i = 0; i < n; ++i) printf("%d %d\n", arr[i].x, arr[i].y);\
    
    return 0;
}

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

요즘 민규네 동네에서는 스타트링크에서 만든 PS카드를 모으는 것이 유행이다.

PS카드는 PS(Problem Solving)분야에서 유명한 사람들의 아이디와 얼굴이 적혀있는 카드이다. 각각의 카드에는 등급을 나타내는 색이 칠해져 있고, 다음과 같이 8가지가 있다.

• 전설카드
• 레드카드
• 오렌지카드
• 퍼플카드
• 블루카드
• 청록카드
• 그린카드
• 그레이카드

카드는 카드팩의 형태로만 구매할 수 있고, 카드팩의 종류는 카드 1개가 포함된 카드팩, 카드 2개가 포함된 카드팩, ... 카드 N개가 포함된 카드팩과 같이 총 N가지가 존재한다.

민규는 카드의 개수가 적은 팩이더라도 가격이 비싸면 높은 등급의 카드가 많이 들어있을 것이라는 미신을 믿고 있다. 따라서, 민규는 돈을 최대한 많이 지불해서 카드 N개 구매하려고 한다. 카드가 i개 포함된 카드팩의 가격은 Pi원이다.

예를 들어, 카드팩이 총 4가지 종류가 있고, P1 = 1, P2 = 5, P3 = 6, P4 = 7인 경우에 민규가 카드 4개를 갖기 위해 지불해야 하는 금액의 최댓값은 10원이다. 2개 들어있는 카드팩을 2번 사면 된다.

P1 = 5, P2 = 2, P3 = 8, P4 = 10인 경우에는 카드가 1개 들어있는 카드팩을 4번 사면 20원이고, 이 경우가 민규가 지불해야 하는 금액의 최댓값이다.

마지막으로, P1 = 3, P2 = 5, P3 = 15, P4 = 16인 경우에는 3개 들어있는 카드팩과 1개 들어있는 카드팩을 구매해 18원을 지불하는 것이 최댓값이다.

카드 팩의 가격이 주어졌을 때, N개의 카드를 구매하기 위해 민규가 지불해야 하는 금액의 최댓값을 구하는 프로그램을 작성하시오. N개보다 많은 개수의 카드를 산 다음, 나머지 카드를 버려서 N개를 만드는 것은 불가능하다. 즉, 구매한 카드팩에 포함되어 있는 카드 개수의 합은 N과 같아야 한다.

첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000)

둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000)

첫째 줄에 민규가 카드 N개를 갖기 위해 지불해야 하는 금액의 최댓값을 출력한다.

dp[1]=card[1]

dp[2]=max(card[2], dp[1]+card[1])

dp[3]=max(card[3], dp[1]+card[2], dp[2]+card[1])

...

#include <stdio.h>

int max(int a, int b){
	return a>b?a:b;
}

int main(void){
	int n;
	scanf("%d", &n);

	int card[10001];
	for(int i=1; i<=n; i++)
		scanf("%d", card+i);

	int dp[1001]={ 0, };
	int maxi=0;

	for(int i=1; i<=n; i++){
		for(int j=0; j<=i; j++)
			maxi=max(card[i-j]+dp[j], maxi);
		dp[i]=maxi;
	}

	printf("%d\n", dp[n]);
}

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

상근이와 선영이가 다른 사람들이 남매간의 대화를 듣는 것을 방지하기 위해서 대화를 서로 암호화 하기로 했다. 그래서 다음과 같은 대화를 했다.

• 상근: 그냥 간단히 암호화 하자. A를 1이라고 하고, B는 2로, 그리고 Z는 26으로 하는거야.
• 선영: 그럼 안돼. 만약, "BEAN"을 암호화하면 25114가 나오는데, 이걸 다시 글자로 바꾸는 방법은 여러 가지가 있어.
• 상근: 그렇네. 25114를 다시 영어로 바꾸면, "BEAAD", "YAAD", "YAN", "YKD", "BEKD", "BEAN" 총 6가지가 나오는데, BEAN이 맞는 단어라는건 쉽게 알수 있잖아?
• 선영: 예가 적절하지 않았네 ㅠㅠ 만약 내가 500자리 글자를 암호화 했다고 해봐. 그 때는 나올 수 있는 해석이 정말 많은데, 그걸 언제 다해봐?
• 상근: 얼마나 많은데?
• 선영: 구해보자!

어떤 암호가 주어졌을 때, 그 암호의 해석이 몇 가지가 나올 수 있는지 구하는 프로그램을 작성하시오.

첫째 줄에 5000자리 이하의 암호가 주어진다. 암호는 숫자로 이루어져 있다.

나올 수 있는 해석의 가짓수를 구하시오. 정답이 매우 클 수 있으므로, 1000000으로 나눈 나머지를 출력한다.

암호가 잘못되어 암호를 해석할 수 없는 경우에는 0을 출력한다.

암호의 해석의 가짓수를 구하는 방법은 다음과 같다.

1. 현재 숫자가 0보다 크다면 바로 앞에서 숫자를 가져온다.
2. 이전의 숫자가 1이거나 이전의 숫자가 2이고 현재 숫자가 6 이하일 경우 전전의 숫자를 가져온다.
   (10~26 사이의 숫자일 경우)

if(cp[i]>0)
     dp[i]=dp[i-1]%1000000;

if(cp[i-1]==1||(cp[i-1]==2&&cp[i]<=6)) 
     dp[i]=(dp[i]+dp[i-2])%1000000;

#include <stdio.h>

int main(void){
	int cp[5001]; // 암호
	int dp[5001]={ 0, };
	
	int i=1;
	dp[0]=1;

	while(scanf("%1d", cp+i)!=EOF) {
		if(cp[i]>0)
			dp[i]=dp[i-1]%1000000;
			
		if(cp[i-1]==1||(cp[i-1]==2&&cp[i]<=6)) 
			dp[i]=(dp[i]+dp[i-2])%1000000;
			
		i++;
	}
	
	printf("%d\n", dp[i-1]%1000000);
}

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

0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 프로그램을 작성하시오.

덧셈의 순서가 바뀐 경우는 다른 경우로 센다(1+2와 2+1은 서로 다른 경우). 또한 한 개의 수를 여러 번 쓸 수도 있다.

첫째 줄에 두 정수 N(1 ≤ N ≤ 200), K(1 ≤ K ≤ 200)가 주어진다.

첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다.

5를 만드는 방법을 생각해보자.

5를 정수 2개로 만드는 방법은 총 6개가 있다.

0+5, 1+4, 2+3, 3+2, 4+1, 5+0

5를 정수 3개로 만드는 방법은 아래와 같다.

0+0+5, 0+1+4, 0+2+3, 0+3+2, 0+4+1, 0+5+0

1+0+4, 1+1+3, 1+2+2, 1+3+1, 1+4+0

2+0+3, 2+1+2, 2+2+1, 2+3+0

3+0+2, 3+1+1, 3+2+0

4+1+0, 4+0+1

5+0+0

dp[n][k]이 정수 k개를 합쳐서 n을 만드는 경우의 수라고 하면 아래와 같은 식을 통해 정수 3개를 더해 5를 만드는 경우의 수를 구할 수 있다. 

dp[5][3]=dp[5][2]+dp[4][2]+dp[3][2]+dp[2][2]+dp[1][2]+dp[0][2]

이를 일반화하면 다음과 같다.

for(int i=1; i<=n; i++){
     for(int j=1; j<=k; j++)
          dp[i][j]=(dp[i-1][j]+dp[i][j-1]);
}

#include <stdio.h>

int main(void){
	int n, k; // 0 ~ n까지의 정수 k개를 더해서 그 합이 n이 되는 경우의 수
	scanf("%d %d", &n, &k);

	int dp[201][201]={ 0, };

	// 초기화
	for(int i=1; i<=k; i++)
		dp[0][i]=1;
	

	for(int i=1; i<=n; i++){
		for(int j=1; j<=k; j++)
			dp[i][j]=(dp[i-1][j]+dp[i][j-1])%1000000000; 
	}

	printf("%d\n", dp[n][k]);
}

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

오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 길이를 k라 했을 때, 그 변에 길이가 k인 정삼각형을 추가한다.

파도반 수열 P(N)은 나선에 있는 정삼각형의 변의 길이이다. P(1)부터 P(10)까지 첫 10개 숫자는 1, 1, 1, 2, 2, 3, 4, 5, 7, 9이다.

N이 주어졌을 때, P(N)을 구하는 프로그램을 작성하시오.

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, N이 주어진다. (1 ≤ N ≤ 100)

각 테스트 케이스마다 P(N)을 출력한다.

파도반 수열은 1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12, 16, 21, 28 순서로 진행이 된다. 또한 위의 그림이 오각형 모양인 것을 확인할 수 있다. 숫자의 관계를 살펴보면 아래의 관계가 성립한다.

dp[i]=dp[i-1]+dp[i-5];

#include <stdio.h>

int main(){
	// 각 테스트 케이스 별 파도반 수열
	long long int dp[101]={ 0, 1, 1, 1, 2, 2, };

	for(int i=6; i<=100; i++)
		dp[i]=dp[i-1]+dp[i-5];
	
	int n, t;
	scanf("%d",&n);

	for(int i=1; i<=n; i++){
		scanf("%d", &t);
		printf("%lld\n", dp[t]);
	}
}

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

3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자.

첫째 줄에 N(1 ≤ N ≤ 30)이 주어진다.

첫째 줄에 경우의 수를 출력한다.

3x1 크기의 벽을 채우는 방법은 존재하지 않는다.

3x2 크기의 벽을 채우는 방법은 총 3가지가 있다.

3x3 크기의 벽을 채우는 방법은 존재하지 않는다.

3x4 크기의 벽을 채우는 방법은 총 11가지가 있다. (3x3+2)

3x5 크기의 벽을 채우는 방법은 존재하지 않는다.

3x6 크기의 벽을 채우는 방법은 총 41가지가 있다. (11x3+3*2+2)

이때 주의할 점은 n이 2씩 증가할 때마다 새로운 경우의 수가 2개씩 추가된다.

for(int i=4; i<=n; i++)
     if(i%2==0){
          dp[i]=dp[i-2]*3;
          for(int j=4; i-j>=0; j+=2)
               dp[i]+=dp[i-j]*2;
     }

#include <stdio.h>

int main(){
	int n;
	scanf("%d",&n);

	int dp[31]={ 1, 0, };

	dp[2]=3;

	for(int i=4; i<=n; i++)
		if(i%2==0){
			dp[i]=dp[i-2]*3;
			for(int j=4; i-j>=0; j+=2)
				dp[i]+=dp[i-j]*2;
		}
		

	printf("%d\n", dp[n]);
}