ITwork

문제

정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다. 섬의 개수를 세는 프로그램을 작성하시오.

한 정사각형과 가로, 세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사각형이다. 

두 정사각형이 같은 섬에 있으려면, 한 정사각형에서 다른 정사각형으로 걸어서 갈 수 있는 경로가 있어야 한다. 지도는 바다로 둘러싸여 있으며, 지도 밖으로 나갈 수 없다.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다.

둘째 줄부터 h개 줄에는 지도가 주어진다. 1은 땅, 0은 바다이다.

입력의 마지막 줄에는 0이 두 개 주어진다.

출력

각 테스트 케이스에 대해서, 섬의 개수를 출력한다.

예제 입력 1 
1 1
0
2 2
0 1
1 0
3 2
1 1 1
1 1 1
5 4
1 0 1 0 0
1 0 0 0 0
1 0 1 0 1
1 0 0 1 0
5 4
1 1 1 0 1
1 0 1 0 1
1 0 1 0 1
1 0 1 1 1
5 5
1 0 1 0 1
0 0 0 0 0
1 0 1 0 1
0 0 0 0 0
1 0 1 0 1
0 0

예제 출력 1 
0
1
1
3
1
9

/*baekjoon 4963 섬의개수*/
#include <bits/stdc++.h>
using namespace std;
#define MAXN 50
int w,h,cnt;
int Map[MAXN+10][MAXN+10];
int dy[] = {-1,1,0,0,-1,-1,1,1};
int dx[] = {0,0,-1,1,-1,1,-1,1};

void DFS(int y, int x){
    if(Map[y][x] != 1) return;
        Map[y][x] = 0;
    for(int i=0; i<8; i++){
        DFS(y+dy[i], x+dx[i]);
    }

}
void Solve(){
    cnt=0;
    for(int i=1; i<=h; i++){
        for(int j=1; j<=w; j++){
            if( Map[i][j]==1){
                DFS(i,j);
                cnt++;
            }
        }
     }
    cout << cnt << endl;
}
void InputData(){
    while(1){
        cin >> w >> h;
        if(w==0 && h==0) break;
        for(int i=1; i<=h; i++){
            for(int j=1; j<=w; j++){
                cin >> Map[i][j];
            }
         }
     Solve();
    }
}
int main(){
    InputData();

    return 0;
}
/*baekjoon 4963 섬의개수*/

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

문제

0보다 크거나 같은 정수 N이 주어진다. 이때, N!을 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 정수 N(0 ≤ N ≤ 12)가 주어진다.

출력

첫째 줄에 N!을 출력한다.

예제 입력 1 
10

예제 출력 1 
3628800

예제 입력 2 
0

예제 출력 2 
1

풀이 

N!은 N=3일 경우 3*2*1로 표시된다. 

예를 들어서 N=3일 경우 어떻게 진행되는지 확인 해 보자.

factorial 함수에 n=3이 전달 되면 아래와 같이 값들이 입력이 될 것이다. 

3*factorial(3-1)

n-1이므로 n=2가 전달되어서 아래와 같이 되고 

3*2*factorial(2-1)

마지막으로 n=1이 전달되면 더이상 factorial함수가 재귀로 호출되지 않고 return 1이 호출되어서 아래 값이 계산되어서 return됨.

3*2*1

최종 출력값은 6이다. 

[소스 코드]

/*baekjoon 10872 팩토리얼*/
#include <bits/stdc++.h>
using namespace std;
int N;
int factorial(int n)
{
    if(n > 1)
        return n*factorial(n-1);
    else
        return 1;
}
void InputData(){
    cin >> N;
}
int main()
{
    InputData();
    cout <<  factorial(N) ;
    return 0;
}
/*baekjoon 10872 팩토리얼*/

문제

숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 몇 개 가지고 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다.

셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 몇 개 가지고 있는 숫자 카드인지 구해야 할 M개의 정수가 주어지며, 이 수는 공백으로 구분되어져 있다. 이 수도 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다.

출력

첫째 줄에 입력으로 주어진 M개의 수에 대해서, 각 수가 적힌 숫자 카드를 상근이가 몇 개 가지고 있는지를 공백으로 구분해 출력한다.

풀이

-오름차순 정렬

-이진 탐색

-Lowerbound

-Upperbound 

/*10816 숫자카드2*/
#include <iostream>
#include <algorithm>
using namespace std;
#define MAXN ((int)5e5+10) 
int N; 
int A[MAXN]; 
int M; 
int B[MAXN]; 
int Temp[MAXN];

void InputData() { 
    cin >> N;
    for(int i=0; i<N; i++) { 
        cin >> A[i]; 
    } 
    cin >> M;
    for(int i=0; i<M; i++) { 
        cin >> B[i]; 
    } 
} 
int BinarySearchLower(int s, int e, int d){
   int m, sol = -1;
    while( s <= e) {
        m = (s+e)/2;
        if( A[m] == d){
            sol = m;
            e = m -1;
        }
        else if (A[m] > d) e = m -1;
        else s = m+1;
    }
    return sol;
}

int BinarySearchUpper(int s, int e, int d){
    int m, sol = -1;
    while( s <= e) {
        m = (s+e) /2;
        if( A[m] == d){
            sol = m;
            s = m +1;
        }
        else if (A[m] > d) e = m -1;
        else s = m + 1;
    }
    return sol;
}

void Solve(){
    sort(A,A+N);
    for(int i=0; i<M; i++) { 
        int lower = BinarySearchLower(0, N-1, B[i] );
        if( lower != -1 ){
            int upper = BinarySearchUpper(0, N-1, B[i] );
            cout <<  upper - lower + 1 << ' '; 
        }else{
            cout <<  0 << ' '; 
        }
    } 
}
int main() { 
    InputData(); 
    Solve();
    return 0; 
} 
/*10816 숫자카드2*/

문제

N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -231 보다 크거나 같고 231보다 작다.

출력

M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다.

예제 입력 1 
5
4 1 5 2 3
5
1 3 7 9 5

예제 출력 1 
1
1
0
0
1

풀이

-오름차순 정렬

1 2 3 4 5

-숫자 1개씩 이진 탐색으로 검색 

중간 값을 구하기 위한 s,e값은 A[] array의 순서이다. 

if s = 0, e = N-1, d=1 부터 시작하면 

m = (s + e)/2; 

m = (0 + 4)/2=2;

A[2] =3이므로 

if(A[m] >d) 이므로 e=m-1로 값을 변경후 다시 찾는다.

s=0, e=1로 값 설정

m=(0+1)/2=0;

if(A[0]==d)에 부합하므로 값을 찾아서 return 1을 전달해 준다. 

/*[1920]수찾기*/
#include <bits/stdc++.h>
using namespace std;
#define MAXN ((int)1e6)
int N;
int A[MAXN +10];
int M;
int X[MAXN+10];

void InputData(){
    cin >> N;
    for(int i =0; i<N; i++){
        cin >> A[i];
    }
    cin >> M;
    for(int i=0; i<M; i++){
        cin >> X[i];
    }
}
bool BinarySearch(int s, int e, int d){
    int m;
    while(s<=e){
        m=(s+e)/2;
        if(A[m]==d) return 1;
        else if(A[m]>d) e=m-1;
        else s = m+1;
    }
    return 0;
}
void Solve(){
    sort(A,A+N);
    for(int i=0; i<M; i++){
        printf("%d\n", BinarySearch(0, N-1, X[i]));
    }
}
int main(){
    InputData();
    Solve();
    return 0;
}
/*[1920]수찾기*/

libray를 이용해서 풀이하면 아래와 같이 간단히 할 수 있다.

http://www.cplusplus.com/reference/algorithm/binary_search/

#include <iostream>
#include <algorithm>
using namespace std;
#define MAXN ((int)1e6+10)
int N,M;
int A[MAXN],X[MAXN];
void Solve(){
    sort(A,A+N);
    for(int i=0; i<M; i++)
        cout<<binary_search(A, A+N, X[i])<<"\n";
}
void InputData(){
    cin >> N;
    for(int i =0; i<N; i++)
        cin >> A[i];
    cin >> M;
    for(int i=0; i<M; i++)
        cin >> X[i];
}
int main(){
    InputData();
    Solve();
    return 0;
}

문제

수를 처리하는 것은 통계학에서 상당히 중요한 일이다. 통계학에서 N개의 수를 대표하는 기본 통계값에는 다음과 같은 것들이 있다. 단, N은 홀수라고 가정하자.

1. 산술평균 : N개의 수들의 합을 N으로 나눈 값
2. 중앙값 : N개의 수들을 증가하는 순서로 나열했을 경우 그 중앙에 위치하는 값
3. 최빈값 : N개의 수들 중 가장 많이 나타나는 값
4. 범위 : N개의 수들 중 최댓값과 최솟값의 차이

N개의 수가 주어졌을 때, 네 가지 기본 통계값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 단, N은 홀수이다. 그 다음 N개의 줄에는 정수들이 주어진다. 입력되는 정수의 절댓값은 4,000을 넘지 않는다.

출력

첫째 줄에는 산술평균을 출력한다. 소수점 이하 첫째 자리에서 반올림한 값을 출력한다.

둘째 줄에는 중앙값을 출력한다.

셋째 줄에는 최빈값을 출력한다. 여러 개 있을 때에는 최빈값 중 두 번째로 작은 값을 출력한다.

넷째 줄에는 범위를 출력한다.

풀이

- data 입력 받기 : N 숫자 개수 

- 먼저 입력된 값을 정렬 한다.그래야 중앙값, 범위를 간단히 계산 해 낼 수 있다. 

- 산술평균, 중앙값,범위는 정렬후 간단히 계산이 가능한데, 중앙값은 좀 더 작업이 필요하다. 

-

/*baekjoon 2108 통계학*/
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;

#define MAXN  ((int)5e5)

int	N;
int Data[MAXN+10]; 
struct MaxData{
	int cnt,val;
};
int A[MAXN+10];
MaxData C[8000+10];
void OutputData(){
	cout << "Frequency : " << endl;
    for(int i = 0; i < 8010; i++){
		if( C[i].cnt >0){
    		cout << C[i].cnt << " " << C[i].val << endl;
		}
    }
}
void InputData(){
    cin >> N;
    for(int i = 0; i < N; i++){
    	cin >> Data[i];
    }
}
bool comp(struct MaxData a, struct MaxData b)
{ 
	if( a.cnt == b.cnt ){
		return a.val < b.val;
	}else{
		return a.cnt > b.cnt;
	}
}
int SortSecond(){
	int maxvalue=0, j=0;
	for(int i=0; i< 8010; i++){
		if(A[i] >0 ){
			if(i<=4000){
				C[j].val=i;
			}
			else{
				C[j].val=4000-i;
			}
			C[j].cnt=A[i];
			j++;
		}
	}
	sort(C, C+8010,comp);
	if(C[0].cnt == C[1].cnt){
		maxvalue= C[1].val;
	}else{
		maxvalue=C[0].val;
	}

	return maxvalue ;
}
void Solve()
{
	double sum=0;
	sort(Data, Data+N);
    for( int i=0; i<N; i++){
		sum += Data[i];
		if( Data[i] >=0){
			A[Data[i]]++;
		} else{
			A[4000-Data[i]]++;
		}
    }
	cout << round(sum/N) << endl;
	cout << Data[N/2] << endl;
	cout << SortSecond() << endl;
	cout << abs(Data[0] - Data[N-1]) << endl;
}
int main()
{
	InputData();
	Solve();
	return 0;
}
/*baekjoon 2108 통계학*/

문제

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

입력

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

출력

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

풀이

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

#define MAX 100001

struct ST{
	int x, y;
};

int	N;
struct ST XYdata[MAX];

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.y < j.y) 
		return true;
	else if (i.y == j.y)
		return (i.x < j.x); 
	else 
		return false;
}

int main()
{
	InputData();
	sort( XYdata, XYdata+N, comp );
	OutputData();

	return 0;
}
/*baekjoon 11651 좌표 정렬하기*/

문제

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

입력

첫째 줄에 정렬하고자하는 수 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 설탕 배달*/

www.acmicpc.net/problem/2751

문제

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

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.

출력

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

2750문제에서 array size만 1000000로 변경하였다. 

/*baekjoon 2751 수 정렬하기2 */
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

#define MAX 1000001

int main()
{
	int data[MAX];
	int i,j, N;
	int tmp, exchg;

	vector<int> v;

	//input data size
	cin >> N;

	//input data
	for(i=0; i<N; i++) {
		cin >> data[i];
		v.push_back(data[i]);
	}

	sort(v.begin(), v.end());
	for(vector<int>::iterator it=v.begin(); it<v.end(); it++)
		printf("%d\n", *it );
		
	return 0;
}
/*baekjoon 2751 수 정렬하기2 */

www.acmicpc.net/problem/2750

문제

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

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.

출력

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

풀이 방법 : 

-입력 받고 

-단순 sorting함수 이용해서 풀면 되는 간단한 문제 

/*baekjoon 2750 수 정렬하기*/
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

#define MAX 1001

int main()
{
	int data[MAX];
	int i,j, N;
	int tmp, exchg;

	vector<int> v;

	//input data size
	cin >> N;

	//input data
	for(i=0; i<N; i++) {
		cin >> data[i];
		v.push_back(data[i]);
	}

	sort(v.begin(), v.end());
	for(vector<int>::iterator it=v.begin(); it<v.end(); it++)
		printf("%d\n", *it );
		
	return 0;
}
/*baekjoon 2750 수 정렬하기*/

이제 좀 코딩 연습을 하고 나서 다시 작성한 내용입니다. 

2021.6.26

  1 /*baekjoon 2750 수 정렬하기*/
  2 #include <iostream>
  3 #include <algorithm>
  4 using namespace std;
  5 #define MAXN 1001
  6 
  7 int N;
  8 int Data[MAXN+10];
  9 
 10 void InputData(){
 11     cin >> N;
 12     for(int i=0; i<N; i++){
 13         cin >> Data[i];
 14     }
 15 }
 16 void Solve(){
 17     for(int i=0; i<N; i++){
 18         cout << Data[i] << endl;
 19     }
 20 }
 21 int main()
 22 {
 23     InputData();
 24     sort(Data, Data+N);
 25     Solve();
 26     return 0;                                                                          
 27 }   
 28 /*baekjoon 2750 수 정렬하기*/

www.acmicpc.net/problem/1712

문제

월드전자는 노트북을 제조하고 판매하는 회사이다. 노트북 판매 대수에 상관없이 매년 임대료, 재산세, 보험료, 급여 등 A만원의 고정 비용이 들며, 한 대의 노트북을 생산하는 데에는 재료비와 인건비 등 총 B만원의 가변 비용이 든다고 한다.

예를 들어 A=1,000, B=70이라고 하자. 이 경우 노트북을 한 대 생산하는 데는 총 1,070만원이 들며, 열 대 생산하는 데는 총 1,700만원이 든다.

노트북 가격이 C만원으로 책정되었다고 한다. 일반적으로 생산 대수를 늘려 가다 보면 어느 순간 총 수입(판매비용)이 총 비용(=고정비용+가변비용)보다 많아지게 된다. 최초로 총 수입이 총 비용보다 많아져 이익이 발생하는 지점을 손익분기점(BREAK-EVEN POINT)이라고 한다.

A, B, C가 주어졌을 때, 손익분기점을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 21억 이하의 자연수이다.

출력

첫 번째 줄에 손익분기점 즉 최초로 이익이 발생하는 판매량을 출력한다. 손익분기점이 존재하지 않으면 -1을 출력한다.

말그대로 수학문제이다. for 나 while로 문제 해결을 하려면 시간초과로 해결이 안된다. 

아래 처럼 수학적으로 생각해서 풀어야 한다. 

/*baekjoon 1712 손익분기점 */
#include <iostream>

using namespace std;

int main(){

	long long A,B,C;
	long long cnt=1;
	long long BEP=0;

	cin >> A >> B >> C;

	if( C - B <= 0) {
		cout << -1 << endl;
	}else if( (C -B) > 0){
		cnt =  A/(C -B); 
		cout << cnt+1 << endl;
	}
	return 0;
}
/*baekjoon 1712 손익분기점 */

www.acmicpc.net/problem/13305

문제

어떤 나라에 N개의 도시가 있다. 이 도시들은 일직선 도로 위에 있다. 편의상 일직선을 수평 방향으로 두자. 제일 왼쪽의 도시에서 제일 오른쪽의 도시로 자동차를 이용하여 이동하려고 한다. 인접한 두 도시 사이의 도로들은 서로 길이가 다를 수 있다. 도로 길이의 단위는 km를 사용한다.

처음 출발할 때 자동차에는 기름이 없어서 주유소에서 기름을 넣고 출발하여야 한다. 기름통의 크기는 무제한이어서 얼마든지 많은 기름을 넣을 수 있다. 도로를 이용하여 이동할 때 1km마다 1리터의 기름을 사용한다. 각 도시에는 단 하나의 주유소가 있으며, 도시 마다 주유소의 리터당 가격은 다를 수 있다. 가격의 단위는 원을 사용한다.

예를 들어, 이 나라에 다음 그림처럼 4개의 도시가 있다고 하자. 원 안에 있는 숫자는 그 도시에 있는 주유소의 리터당 가격이다. 도로 위에 있는 숫자는 도로의 길이를 표시한 것이다. 

제일 왼쪽 도시에서 6리터의 기름을 넣고, 더 이상의 주유 없이 제일 오른쪽 도시까지 이동하면 총 비용은 30원이다. 만약 제일 왼쪽 도시에서 2리터의 기름을 넣고(2×5 = 10원) 다음 번 도시까지 이동한 후 3리터의 기름을 넣고(3×2 = 6원) 다음 도시에서 1리터의 기름을 넣어(1×4 = 4원) 제일 오른쪽 도시로 이동하면, 총 비용은 20원이다. 또 다른 방법으로 제일 왼쪽 도시에서 2리터의 기름을 넣고(2×5 = 10원) 다음 번 도시까지 이동한 후 4리터의 기름을 넣고(4×2 = 8원) 제일 오른쪽 도시까지 이동하면, 총 비용은 18원이다.

각 도시에 있는 주유소의 기름 가격과, 각 도시를 연결하는 도로의 길이를 입력으로 받아 제일 왼쪽 도시에서 제일 오른쪽 도시로 이동하는 최소의 비용을 계산하는 프로그램을 작성하시오.

입력

표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1개의 자연수로 주어진다. 다음 줄에는 주유소의 리터당 가격이 제일 왼쪽 도시부터 순서대로 N개의 자연수로 주어진다. 제일 왼쪽 도시부터 제일 오른쪽 도시까지의 거리는 1이상 1,000,000,000 이하의 자연수이다. 리터당 가격은 1 이상 1,000,000,000 이하의 자연수이다. 

출력

표준 출력으로 제일 왼쪽 도시에서 제일 오른쪽 도시로 가는 최소 비용을 출력한다. 

풀이과정 

변수 type을 long long으로 해야함.

아래 반례가 제대로 동작하면 맞을 수 있다. 

반례 

5
3 2 1 4
5 8 9 4 1

5*3=15

5*2=10

5*1=5

4*4=16

total=46

/* baekjoon 13305 주유소 */
#include <iostream>
using namespace std;

#define Max 100001
long long Distance[Max];
long long price[Max];
int N;

void InputData(){
    cin >> N;
    for(int i =0; i < N-1; i++)
        cin >> Distance[i];

    for(int i =0; i < N; i++)
        cin >> price[i];
}
void Solve(){
    long long result=0;
    long long minPrice;
 
    result += Distance[0] * price[0];
    minPrice = price[0];
    for(int i = 1; i < N-1 ; i++){
        if( price[i] > minPrice ){
            result += Distance[i] * minPrice;
        }else{
            minPrice = price[i];
            result += Distance[i] * minPrice;
        }
    }
    cout << result << endl;
}

int main(){
    InputData();
    Solve(); 
    return 0;
}
/* baekjoon 13305 주유소 */

www.acmicpc.net/problem/1541

문제

세준이는 양수와 +, -, 그리고 괄호를 가지고 식을 만들었다. 그리고 나서 세준이는 괄호를 모두 지웠다.

그리고 나서 세준이는 괄호를 적절히 쳐서 이 식의 값을 최소로 만들려고 한다.

괄호를 적절히 쳐서 이 식의 값을 최소로 만드는 프로그램을 작성하시오.

입력

첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 많이 연속되는 숫자는 없다. 수는 0으로 시작할 수 있다. 입력으로 주어지는 식의 길이는 50보다 작거나 같다.

출력

첫째 줄에 정답을 출력한다.

풀과정

1. 입력 받기

2. parsing

3.연산자와 숫자 구분

4. 연산자에 따라 연산 해서 결과 출력 

/* baekjoon 1541 잃어버린 괄호*/
#include <iostream>
#include <string>

using namespace std;

int main(){

	string str;
	string tmp="";
	int i,j, result=0;
	bool  minus =false;
	cin >> str;

	for( i = 0; i <= str.size(); i++){

		if( str[i] == '+' || str[i] == '-' || str[i] == '\0' ){

			if( minus ){
				result -= stoi(tmp);
			}else{

				result += stoi(tmp);
			}

			if( str[i] == '-' )
				minus = true;
			tmp = "";
			continue;
		}
		tmp += str[i];
	} //for
	cout << result << endl;
	return 0;
}
/* baekjoon 1541 잃어버린 괄호*/

www.acmicpc.net/problem/11399

문제

인하은행에는 ATM이 1대밖에 없다. 지금 이 ATM앞에 N명의 사람들이 줄을 서있다. 사람은 1번부터 N번까지 번호가 매겨져 있으며, i번 사람이 돈을 인출하는데 걸리는 시간은 Pi분이다.

사람들이 줄을 서는 순서에 따라서, 돈을 인출하는데 필요한 시간의 합이 달라지게 된다. 예를 들어, 총 5명이 있고, P1 = 3, P2 = 1, P3 = 4, P4 = 3, P5 = 2 인 경우를 생각해보자. [1, 2, 3, 4, 5] 순서로 줄을 선다면, 1번 사람은 3분만에 돈을 뽑을 수 있다. 2번 사람은 1번 사람이 돈을 뽑을 때 까지 기다려야 하기 때문에, 3+1 = 4분이 걸리게 된다. 3번 사람은 1번, 2번 사람이 돈을 뽑을 때까지 기다려야 하기 때문에, 총 3+1+4 = 8분이 필요하게 된다. 4번 사람은 3+1+4+3 = 11분, 5번 사람은 3+1+4+3+2 = 13분이 걸리게 된다. 이 경우에 각 사람이 돈을 인출하는데 필요한 시간의 합은 3+4+8+11+13 = 39분이 된다.

줄을 [2, 5, 1, 4, 3] 순서로 줄을 서면, 2번 사람은 1분만에, 5번 사람은 1+2 = 3분, 1번 사람은 1+2+3 = 6분, 4번 사람은 1+2+3+3 = 9분, 3번 사람은 1+2+3+3+4 = 13분이 걸리게 된다. 각 사람이 돈을 인출하는데 필요한 시간의 합은 1+3+6+9+13 = 32분이다. 이 방법보다 더 필요한 시간의 합을 최소로 만들 수는 없다.

줄을 서 있는 사람의 수 N과 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어졌을 때, 각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000)

출력

첫째 줄에 각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값을 출력한다.

/* baekjoon 11399 ATM */
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main(){

	int N;
	int i,j, count=0, tmp =0;
	int start, finish;
	cin >> N;
	vector< int> v;

	for( int i =0; i < N; i++){
		cin >> start;
		v.push_back( start );
	}

	sort( v.begin(), v.end() );

	for( i =0; i< N; i++ ){
		tmp = 0;
		for(j =0; j<=i; j++){
			tmp += v[j];
		}
		count += tmp;
	}//for

	cout << count << endl;
	return 0;
}
/* baekjoon 11399 ATM */

www.acmicpc.net/problem/1931

문제

한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.

입력

첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 231-1보다 작거나 같은 자연수 또는 0이다.

출력

첫째 줄에 최대 사용할 수 있는 회의의 최대 개수를 출력한다.

아직 틀렸다고 나옴. 

#include <iostream>
#include <queue>

using namespace std;

int main(){

	int N;
	int i, count=0, tmp = 0;
	int start, finish;
	cin >> N;
	queue< pair<int, int> > q;

	for( int i =0; i < N; i++){
		cin >> start >> finish;
		q.push(make_pair(start, finish));
	}
	tmp = q.front().second;
	q.pop();
	count =1;

	while( !q.empty() ){

		if( q.front().first >= tmp ){
			++count;
			tmp = q.front().second;
			q.pop();
		} else{
			q.pop();
		}
	}


	cout << count << endl;
	return 0;
}

input의 순서를 바꿔서 끝나는 시간을 첫번째로 오게 한다음 sorting을 해야 한다. 

끝나는 시간 기준으로 오름 차순으로 sorting을 한다. 그리고 시작시간이  끝나는 시간과 겹치지 않는 회의시간만 찾아내면 된다.

드디어 아래 코드는 맞다고 출력이 되었다. 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main(){

	int N;
	int i, count=0, tmp =0;
	int start, finish;
	cin >> N;
	vector< pair<int, int> > v;

	for( int i =0; i < N; i++){
		cin >> start >> finish;
		v.push_back(make_pair( finish, start));
	}

	sort( v.begin(), v.end() );

	for( i =0; i< N; i++ ){

		if( v[i].first == v[i].second ){
				tmp = v[i].first;
				count++;
		}else{
			if( v[i].second >= tmp ){
				count++;
				tmp = v[i].first;
			}
		}

	}//for

	cout << count << endl;
	return 0;
}