ITwork

문제

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

입력

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

출력

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

풀이

-sort함수를 이용한 정렬 문제

-sort의 비교함수의 조건만 추가 하면 풀이됨.

  x 좌표 증가할경우와 y조표가 같을 경우에 대한 조건만 추가하면 됨.

/*baekjoon 11650 좌표 정렬하기*/
#include <iostream>
#include <algorithm>
using namespace std;

#define MAXN 100000
int	N;
struct ST{
	int x, y;
};
struct ST XYdata[MAXN+10];

void InputData(){
	//input data size
    scanf("%d", &N);
	//input data
    for( int i=0; i<N; i++ ){
    scanf("%d %d", &XYdata[i].x, &XYdata[i].y );
    }
}
void OutputData(){
	for( int i=0; i<N; i++){
		printf("%d %d", XYdata[i].x, XYdata[i].y);
	printf("\n");
	}
}
bool comp(struct ST i, struct ST j){ 
	if (i.x < j.x) 
		return true;
	else if (i.x == j.x)
		return (i.y < j.y); 
	else 
		return false;
}
int main()
{
	InputData();
	sort( XYdata, XYdata+N, comp );
	OutputData();
	return 0;
}
/*baekjoon 11650 좌표 정렬하기*/

문제

배열을 정렬하는 것은 쉽다. 수가 주어지면, 그 수의 각 자리수를 내림차순으로 정렬해보자.

입력

첫째 줄에 정렬하고자하는 수 N이 주어진다. N은 1,000,000,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 자리수를 내림차순으로 정렬한 수를 출력한다.

풀이 

- sort를 이용한 단순 정렬 문제 

  1 /*baekjoon 1427 소트인사이드*/
  2 #include <iostream>
  3 #include <algorithm>
  4 #include <string>
  5 using namespace std;
  6 
  7 string N;
  8 void InputData(){
  9     cin >> N;
 10 }
 11 bool comp(string a, string b){ return a < b;}
 12 void Solve(){
 13     sort(N.rbegin(),N.rend());
 14     cout << N << endl;
 15 }
 16 int main(){
 17     InputData();
 18     Solve();
 19     return 0;
 20 }
 21 /*baekjoon 1427 소트인사이드*/   

문제

알파벳 소문자로 이루어진 N개의 단어가 들어오면 아래와 같은 조건에 따라 정렬하는 프로그램을 작성하시오.

1. 길이가 짧은 것부터
2. 길이가 같으면 사전 순으로

입력

첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다.

출력

조건에 따라 정렬하여 단어들을 출력한다. 단, 같은 단어가 여러 번 입력된 경우에는 한 번씩만 출력한다.

풀이

-sort를 이용한 단순 정렬 문제

-strcmp대신 c++에서 사용하는 str[i].compare(str[i+1])를 사용함 

/*baekjoon 1181 단어 정렬*/
#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;

#define MAX 20000
int	N;
string Data[MAX+10];

void InputData(){
	cin >> N;
	for(int i = 0; i < N; i++){
		cin >> Data[i];
	}
}
void OutputData(){
	for( int i=0; i<N; i++){
		cout << Data[i]<< endl;
	}
}
bool comp(string i, string j){ 
    if (i.size() == j.size()){
        return (i < j);
    }
    else{
        return i.size() < j.size();
    }
}
void Solve(){
	cout << Data[0] << endl;	
	for(int i=0; i<N-1; i++){
		if(Data[i].compare(Data[i+1]) ){
			cout << Data[i+1] << endl;	
		}
	}
}
int main()
{
	InputData();
	sort( Data, Data+N, comp);
	Solve();
	return 0;
}
/*baekjoon 1181 단어 정렬*/

문제

시골에 있는 태양이의 삼촌 댁에는 커다란 참외밭이 있다. 문득 태양이는 이 밭에서 자라는 참외가 도대체 몇 개나 되는지 궁금해졌다. 어떻게 알아낼 수 있는지 골똘히 생각하다가 드디어 좋은 아이디어가 떠올랐다. 유레카! 1m^2의 넓이에 자라는 참외 개수를 헤아린 다음, 참외밭의 넓이를 구하면 비례식을 이용하여 참외의 총개수를 구할 수 있다.

1m^2의 넓이에 자라는 참외의 개수는 헤아렸고, 이제 참외밭의 넓이만 구하면 된다. 참외밭은 ㄱ-자 모양이거나 ㄱ-자를 90도, 180도, 270도 회전한 모양(┏, ┗, ┛ 모양)의 육각형이다. 다행히도 밭의 경계(육각형의 변)는 모두 동서 방향이거나 남북 방향이었다. 밭의 한 모퉁이에서 출발하여 밭의 둘레를 돌면서 밭경계 길이를 모두 측정하였다.

예를 들어 참외밭이 위 그림과 같은 모양이라고 하자. 그림에서 오른쪽은 동쪽, 왼쪽은 서쪽, 아래쪽은 남쪽, 위쪽은 북쪽이다. 이 그림의 왼쪽위 꼭짓점에서 출발하여, 반시계방향으로 남쪽으로 30m, 동쪽으로 60m, 남쪽으로 20m, 동쪽으로 100m, 북쪽으로 50m, 서쪽으로 160m 이동하면 다시 출발점으로 되돌아가게 된다.

위 그림의 참외밭  면적은 6800m^2이다. 만약 1m^2의 넓이에 자라는 참외의 개수가 7이라면, 이 밭에서 자라는 참외의 개수는 47600으로 계산된다.

1m^2의 넓이에 자라는 참외의 개수와, 참외밭을 이루는 육각형의 임의의 한 꼭짓점에서 출발하여 반시계방향으로 둘레를 돌면서 지나는 변의 방향과 길이가 순서대로 주어진다. 이 참외밭에서 자라는 참외의 수를 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에 1m^2의 넓이에 자라는 참외의 개수를 나타내는 양의 정수 K (1≤K≤20)가 주어진다. 참외밭을 나타내는 육각형의 임의의 한 꼭짓점에서 출발하여 반시계방향으로 둘레를 돌면서 지나는 변의 방향과 길이 (1 이상 500 이하의 정수) 가 둘째 줄부터 일곱 번째 줄까지 한 줄에 하나씩 순서대로 주어진다. 변의 방향에서 동쪽은 1, 서쪽은 2, 남쪽은 3, 북쪽은 4로 나타낸다.

출력

첫째 줄에 입력으로 주어진 밭에서 자라는 참외의 수를 출력한다.

풀이 

-면적을 구하는 방법 생각 (백준 2166과 동일한 방식으로 풀면 되나 입력이 달라서 좌표로 변환하는 부분이 추가되어야 합니다.)

-SW에서는 아래 신발끈 공식을 이용해서 면적을 구해야 함.

https://ko.wikipedia.org/wiki/%EC%8B%A0%EB%B0%9C%EB%81%88_%EA%B3%B5%EC%8B%9D

/*baekjoon 2477 참외밭*/
#include <iostream>
#include <algorithm>
using namespace std;

#define MAX 10010

struct Coordinate{
	int d;
	int length;
};

struct ST{
	int x;
	int y;
};

int	N;
struct Coordinate C[MAX];
struct ST CD[MAX];

void InputData(){
	//input data size
	cin >> N;
	//input data
	for(int i = 0; i < 6; i++){
		cin >> C[i].d >> C[i].length;
	}
}

void OutputData(){
	for( int i=0; i<N; i++){
	printf("\n");
	}
}

void ChangeCoord(){
	CD[0].x = 0;
	CD[0].y = 0;

	for(int i=0; i<6; i++){

		if( C[i].d == 1){
			CD[i+1].x = CD[i].x - C[i].length;
			CD[i+1].y += CD[i].y;
		}else if( C[i].d ==2 ){
			CD[i+1].x = CD[i].x + C[i].length;
			CD[i+1].y += CD[i].y;
		}else if( C[i].d == 3){
			CD[i+1].x += CD[i].x;
			CD[i+1].y = CD[i].y - C[i].length;
		}else if( C[i].d == 4){
			CD[i+1].x += CD[i].x;
			CD[i+1].y = CD[i].y + C[i].length;
		}

	}

}

int Solve(){
	int Sum=0;
	ChangeCoord();	
	for(int i=0; i<6; i++){
		int idx;
		idx = (i+1) % 6;
		Sum += (CD[i].x * CD[idx].y - CD[idx].x * CD[i].y );
	}
	return abs(Sum)/2.0;
}

int main()
{
	int ans=0;
	cout.precision(1);
	cout << fixed;
	InputData();
	ans = Solve();	
	cout << ans*N << endl;
	return 0;
}
/*baekjoon 2477 참외밭*/

문제

2차원 평면상에 N(3 ≤ N ≤ 10,000)개의 점으로 이루어진 다각형이 있다. 이 다각형의 면적을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. 다음 N개의 줄에는 다각형을 이루는 순서대로 N개의 점의 x, y좌표가 주어진다. 좌표값은 절댓값이 100,000을 넘지 않는 정수이다.

출력

첫째 줄에 면적을 출력한다. 면적을 출력할 때에는 소수점 아래 둘째 자리에서 반올림하여 첫째 자리까지 출력한다.

풀이 

-면적을 구하는 방법 생각 

-SW에서는 아래 신발끈 공식을 이용해서 면적을 구해야 함.

https://ko.wikipedia.org/wiki/%EC%8B%A0%EB%B0%9C%EB%81%88_%EA%B3%B5%EC%8B%9D

/*baekjoon 2166 다각형 면적 */
#include <iostream>
#include <algorithm>
using namespace std;

#define MAX 10010

struct ST{
	double x;
	double y;
};

int	N;
struct ST CD[MAX];

void InputData(){
	//input data size
	cin >> N;
	//input data
	for(int i = 0; i < N; i++){
		cin >> CD[i].x >> CD[i].y;
	}
}

void OutputData(){
	for( int i=0; i<N; i++){
	printf("\n");
	}
}

double Solve(){
	double Sum=0;
	
	for(int i=0; i<N; i++){
		int idx;
		idx = (i+1) % N;
		Sum += (CD[i].x * CD[idx].y - CD[idx].x * CD[i].y );
	}
	return abs(Sum)/2.0;
}

int main()
{
	double ans=0;
	cout.precision(1);
	cout << fixed;
	InputData();
	ans = Solve();	
	cout << ans << endl;
	return 0;
}
/*baekjoon 2166 다각형 면적 */

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

문제

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다.

출력

첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

/*baekjoon 10989  수 정렬하기 3*/
#include <iostream>
#include <algorithm>
using namespace std;

#define MAX 10001

int	N;
int NumData[MAX] = {0}; 

void InputData(){
	int tmp=0;
	//input data size
	cin >> N;
	//input data
	for(int i = 0; i < N; i++){
        scanf("%d", &tmp);
		NumData[tmp]++;
	}
}

void OutputData(){
	for( int i=0; i<MAX; i++){
		if(NumData[i]){
			for(int count=0; count<NumData[i]; count++)
				printf("%d\n", i);
		}
	}
}

int main()
{
	InputData();
	OutputData();

	return 0;
}
/*baekjoon 10989  수 정렬하기 3*/

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

문제

온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다. 이때, 회원들을 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을 작성하시오.

입력

첫째 줄에 온라인 저지 회원의 수 N이 주어진다. (1 ≤ N ≤ 100,000)

둘째 줄부터 N개의 줄에는 각 회원의 나이와 이름이 공백으로 구분되어 주어진다. 나이는 1보다 크거나 같으며, 200보다 작거나 같은 정수이고, 이름은 알파벳 대소문자로 이루어져 있고, 길이가 100보다 작거나 같은 문자열이다. 입력은 가입한 순서로 주어진다.

출력

첫째 줄부터 총 N개의 줄에 걸쳐 온라인 저지 회원을 나이 순, 나이가 같으면 가입한 순으로 한 줄에 한 명씩 나이와 이름을 공백으로 구분해 출력한다.

/*baekjoon 10814 나이순 정렬*/
#include <iostream>
#include <algorithm>
using namespace std;

#define MAX 100001

struct ST{
	int age;
	char name[110];
};

int	N;
struct ST PersonData[MAX];

void InputData(){
	//input data size
	cin >> N;
	//input data
	for(int i = 0; i < N; i++){
		cin >> PersonData[i].age >> PersonData[i].name;
	}
}

void OutputData(){
	for( int i=0; i<N; i++){
		printf("%d %s", PersonData[i].age, PersonData[i].name);
	printf("\n");
	}
}

bool Comp_age(struct ST i, struct ST j){ return (i.age < j.age);}
bool Comp_name(struct ST i, struct ST j){ return (i.name < j.name);}

int main()
{
	InputData();
	stable_sort( PersonData, PersonData+N, Comp_age);
	OutputData();

	return 0;
}
/*baekjoon 10814 나이순 정렬*/

www.acmicpc.net/problem/2839

문제

상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그램 봉지와 5킬로그램 봉지가 있다.

상근이는 귀찮기 때문에, 최대한 적은 봉지를 들고 가려고 한다. 예를 들어, 18킬로그램 설탕을 배달해야 할 때, 3킬로그램 봉지 6개를 가져가도 되지만, 5킬로그램 3개와 3킬로그램 1개를 배달하면, 더 적은 개수의 봉지를 배달할 수 있다.

상근이가 설탕을 정확하게 N킬로그램 배달해야 할 때, 봉지 몇 개를 가져가면 되는지 그 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (3 ≤ N ≤ 5000)

출력

상근이가 배달하는 봉지의 최소 개수를 출력한다. 만약, 정확하게 N킬로그램을 만들 수 없다면 -1을 출력한다.

/*baekjoon 2839 설탕 배달*/
#include <iostream>

using namespace std;

int N; // 설탕 무게 

void InputData(){
	cin >> N;
}

void Solve()
{
	int total = 0;
	int tmp = 0;

	if( N%5 == 0 ){
		cout <<  N/5 << endl;
	}else {
		tmp = N/5;	
		do{
			if( (N - tmp*5)%3 == 0){
				cout << tmp + (N -5*tmp)/3 << endl;
				break; 
			}
			tmp--;
		}while(tmp >=0 );
	}	

	if( tmp == -1 )
		cout << "-1" << endl;
}

int main()
{
	InputData();
	Solve();

	return 0;
}
/*baekjoon 2839 설탕 배달*/