IPv4

위의 문제를 이해하는데에 시간이 조금 걸렸습니다.

[ 문제 해석 ]

1. 문제의 목표

한 행 또는 한 열 전부에서 한쪽 끝에서 다른쪽 끝까지 지나갈 수 있는 길의 갯수를 구해라

N*N 배열에 각 숫자들이 들어가 있습니다.

그 숫자들은 각각의 높이를 가리킵니다.

아래 배열 표에서 1행은 각각 3 3 3 3 3 3 의 높이를 가집니다.

2. 지나갈 수 있는 조건

 1) 길에 속한 모든 칸의 높이가 같은 경우

 2) 또는 지나갈 수 있는 경사로를 만들어서 지나가는 방법

3. 경사로의 특징

 1) 높이 차이가 항상 1이다.

 2) 경사로는 낮은 칸에 놓는다.

 3) L개의 연속된 칸에 경사로 바닥이 모두 접해야 한다.

 4) 경사로를 놓을 낮은 칸의 높이는 모두 같아야 한다.

4. 경사로를 놓지 못하는 경우

 1) 경사로를 놓은 곳에 또 경사로를 놓는 경우

 2) 낮은 칸과 높은 칸의 차이가 1이 아닌 경우

 3) 낮은 지점의 칸의 높이가 모두 같지 않거나, L개가 연속되지 않는 경우

 4) 경사로 때문에 배열의 범위를 벗어난 경우

[ 경사로 놓을 수 있는 예시 ]

[ 경사로를 놓지 못하는 경우 ]

왼쪽부터 1,2,3,4 번으로 부르겠습니다.

- 1번 : 높이 1을 높여도 3까지 닿지 못함

- 2번 : 경사로 바닥이 닿지 않음

- 3번 : 경사로가 겹침

- 4번 : 경사로 바닥이 닿지 않음

[ 문제 풀이 과정 ]

1. 행과 열에서 지나갈 수 있는 길을 구하는 함수를 각각 만들어 준다.

2. 만약 있는 경우 1을 return 하고, 없는 경우 0을 return 하여 각 행렬을 모두 순회한다.

3. 함수 내부에서 N만큼의 크기를 갖는 Buffer 라는 임시 배열을 만든다.

4. 만약 road 배열에서 해당 인덱스 다음 인덱스가 숫자가 더 크면 오르막길이고, 낮으면 내리막길이다.

5. 내리막길인 경우, i인덱스에 올라올 수 있는 길을 만들어야 하므로 i의 다음 인덱스부터 L까지에 해당하는 경사로를 놓아준다.

6. 만약 위의 경사로를 놓을 수 없는 경우가 없다면 Buffer에 해당 자리의 카운트를 증가시킨다.

7. 행을 탐색한 경우 모든 행을 탐색하고 마지막으로 Buffer 내부 원소 값을 비교해 1보다 큰 경우 중첩되는 경우 이므로,

   갈 수 없는 길로 0을 리턴해준다.

8. 모든 조건이 맞는다면 1을 리턴해준다.

이와 같은 방식을 행열에 모두 적용해주면 됩니다.

[ 소스코드 ]

import java.util.Scanner;

public class 경사로 {

    // 백준 코드로 제출시 Main 으로 제출

    // 입력
    static int N, L;
    static int answer = 0;
    static int[][] road;

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        L = sc.nextInt();

        road = new int[N][N];

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                road[i][j] = sc.nextInt();
            }
        }

        for (int i = 0; i < N; i++) {
            answer += roadCol(i) + roadRow(i);
        }

        System.out.println(answer);
    }

    public static int roadCol(int idx) {

        int[] Buffer = new int[N]; // 초기값 : 0

        // 만약 배열이 차이가 없는 경우에는 초기 값이 그대로 유지됨

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

            //높이 차이가 2이상 나는 경우
            try {
                if (road[idx][i] >= road[idx][i + 1] + 2) {
                    return 0;
                }
                if (road[idx][i] <= road[idx][i + 1] - 2) {
                    return 0;
                }

                if (road[idx][i] > road[idx][i + 1]) { // 내리막
                    int start = i + 1;
                    int j;
                    for (j = start; j < start + L; j++) {
                        if (j >= N) return 0; // 범위를 벗어난 경우
                        if (road[idx][i + 1] == road[idx][j]) { // 다음 블럭의 높이가 같은 경우 버퍼에 넣어줌
                            Buffer[j]++;
                        } else return 0;
                    }
                }
                else if (road[idx][i] < road[idx][i + 1]) { // 오르막
                    int start = i;
                    int j;
                    for (j = start; j > start - L; j--) {
                        if (j < 0) return 0; // 범위가 넘으면 종료
                        if (road[idx][i] == road[idx][j]) {
                            Buffer[j]++;
                        } else return 0;
                    }
                }
            } catch (Exception e) {

            }
        }

        for (int i = 0; i < N; i++) {
            if(Buffer[i] > 1) return 0;
        }

        return 1;
    }

    public static int roadRow(int idx) {
        int[] buffer = new int[N];

        for (int i = 0; i < N; i++) {
            try {
                if (road[i][idx] >= road[i + 1][idx] + 2) {
                    return 0;
                }
                if (road[i][idx] <= road[i + 1][idx] - 2) {
                    return 0;
                }

                if (road[i][idx] > road[i + 1][idx]) { // 오르막
                    int start = i + 1;
                    for (int j = start; j < start + L; j++) {
                        if (j >= N) return 0;
                        if (road[i + 1][idx] == road[j][idx]) {
                            buffer[j]++;
                        } else return 0;
                    }
                }

                if (road[i][idx] < road[i + 1][idx]) { // 내리막
                    int start = i;
                    for (int j = start; j > start - L; j--) {
                        if (j < 0) return 0;
                        if (road[i][idx] == road[j][idx]) {
                            buffer[j]++;
                        } else return 0;
                    }
                }
            } catch (Exception e) {

            }
        }

        for (int i = 0; i < N; i++) {
            if(buffer[i] > 1) return 0;
        }

        return 1;
    }
}

[ 참고 ]

백준에서 코드 제출할 때는 클래스 명을 Main 으로 작성해서 제출해야 합니다.

위의 코드를 그대로 제출할 시 컴파일 에러가 발생합니다.

* 참조 : https://www.youtube.com/watch?v=PCURy3Wv8uU

< 알아야하는 개념 >

1. 절대값 함수

    : stdlib 헤더에 있으며, abs ( value ) 를 하면 절대값을 출력해준다.

2. cout 으로 소수점 반올림 시키기

    : cout.precision(0) 하면 정수 부분만 출력이 된다.

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

bool compare(int a,int b){
    return a < b;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n,temp,arr[8001]; // 음~양수 4000씩 = 8000
    int mx = -1,mode,count = 0;
    double sum = 0;

    vector <int> vec,mode_vec;

    for(int i=0; i<n; i++){
        arr[i] = 0;
    }

    cin >> n;

    for(int i=0; i<n; i++){
        cin >> temp;
        vec.push_back(temp);
        sum += temp;
        temp = (temp <= 0) ? abs(temp) : temp + 4000;
        arr[temp]++;
        if(arr[temp] > mx){
            mx = arr[temp];
            mode = temp;
        }
    }

    sort(vec.begin(),vec.end(),compare);

    for(int i=0; i<8001; i++){
        if(arr[i] == mx){
            mode = i;
            mode = (mode<4000) ? -mode : mode-4000;
            mode_vec.push_back(mode);
        }
    }

    sort(vec.begin(),vec.end(),compare);

    mode = (mode_vec.size() >= 2) ? mode_vec[1] : mode_vec[0];
    double eve = sum/double(n);
    cout.precision(0);
    cout << eve << endl;
    cout << vec[n/2] << endl;
    cout << mode << endl;
    cout << vec[vec.size()-1] - vec[0] << endl;

    return 0;
}

< Vector 와 Array 의 차이점 >

Vector 는 삽입/삭제가 빈번하게 일어나는 곳에서 유리한 동적인 자료구조

Array 는 고정된 크기로 연속된 메모리를 가지고 있어 삽입/삭제가 빈번하지 않다면 Vector 보다 더 유리한 정적인 자료구조

< ios::sync_with_stdio(false);>

cin과 cout의 속도가 C의 입출력 속도에 비해 떨어지기 때문에 저 코드를 사용해 속도를 높이는 기능으로 사용한다.

하지만 C의 입출력 함수를 아예 못쓰게되서 사용할때 주의할 필요가 있다.

< cin.tie(NULL); cout.tie(NULL); >

입력과 출력을 여러 번 번갈아가며 반복해야 하는 경우 필수적으로 cin.tie(null); 코드를 추가하여 cout과 cin의 묶음을 풀어줘야 합니다.그래서 해당 코드를 통해 최적화를 시켜주는 것입니다.

#include <iostream>

using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n,tmp;
    int arr[10001] = {0};

    cin >> n;

    for(int i=0; i<n; i++){
        cin >> tmp;
        arr[tmp] += 1; // 해당 숫자에 삽입
    }

    for(int i=1; i<= 10000; i++){
        for(int j = 0; j < arr[i]; j++)
            cout << i << "\n";
    }

    return 0;
}

< C++ STL ( sort ) >

- sort ( arr, arr+n ) : 오름차순 정렬

- sort ( arr, arr+n, desc ) : 내림차순 정렬 ( desc 함수를 구현해줘야함 )

내림차순 정렬

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

#define max 1000000

bool desc(int a,int b){
    return a > b;
}

int main(){
    int n,arr[max];
    cin >> n;

    for(int i=0; i<n; i++){
        cin >> arr[i];
    }

    sort(arr,arr+n,desc);

    for(int i=0; i<n; i++){
        cout << arr[i];
    }

    return 0;
}

- 오름차순 정렬 ( 정답 )

* 여기서 중요한 점은 endl 하면 시간초과이고, '\n' 은 정답이라는 것이다. 그 이유는 블로그에 설명을 해놨다.

https://blog.naver.com/PostView.naver?blogId=tjdwns4537&Redirect=View&logNo=222434654089&categoryNo=89&isAfterWrite=true&isMrblogPost=false&isHappyBeanLeverage=true&contentLength=13514

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

#define max 1000000

int main(){
    int n,arr[max];
    cin >> n;

    for(int i=0; i<n; i++){
        cin >> arr[i];
    }

    sort(arr,arr+n);

    for(int i=0; i<n; i++){
        cout << arr[i];
    }

    return 0;
}

< Pair > 과 start,second

헤더 :  utility 

개념 :

pair < [type1] [type2] > p    :    사용할 데이터타입 1,2 를 넣고 그 타입의 pair 클래스인 p 생성

p.first    :    p의 첫번째 인자를 반환

p.second    :    p의 두번째 인자를 반환

make_fair(변수1,변수2)    :    변수1,2가 들어간 pair 를 생성

operator 사용가능

sort 알고리즘으로 정렬 가능

#include <iostream>
#include <utility>
#include <algorithm>

using namespace std;

#define max 50

string board[max];

int wb_cnt(string WB[],int x,int y){
    int cnt = 0;
    for(int i=0; i<8; i++){
        for(int j=0; j<8; j++){
            if(board[x+i][y+j] != WB[i][j]) cnt++;
        }
    }
    return cnt;
}

int bw_cnt(string BW[],int x,int y){
    int cnt = 0;
    for(int i=0; i<8; i++){
        for(int j=0; j<8; j++){
            if(board[x+i][y+j] != BW[i][j]) cnt++;
        }
    }
    return cnt;
}

int main(){
    string WB[8] = {
        "WBWBWBWB",
        "BWBWBWBW",
        "WBWBWBWB",
        "BWBWBWBW",
        "WBWBWBWB",
        "BWBWBWBW",
        "WBWBWBWB",
        "BWBWBWBW"
    };
    string BW[8] = {
        "BWBWBWBW",
        "WBWBWBWB",
        "BWBWBWBW",
        "WBWBWBWB",
        "BWBWBWBW",
        "WBWBWBWB",
        "BWBWBWBW",
        "WBWBWBWB"
    };

    int MIN = 999999;
    int cnt,tmp;
    pair<int,int> p;
    cin >> p.first >> p.second;
    for(int i=0; i<p.first; i++){
        cin >> board[i];
    }

    for(int i=0; i+8 <= p.first; i++){
        for(int j=0; j+8 <= p.second; j++){
            // 8*8 크기로 짤라내기만 하면 되므로 +8을 해줌
            tmp = min(wb_cnt(WB,i,j),bw_cnt(BW,i,j));
            if(tmp < MIN) MIN = tmp;
        }
    }
    cout << MIN;
    return 0;
}

#include <iostream>
using namespace std;

class phy{
    int weight;
    int tall;
    int cnt;
    public:
    phy():weight(0),tall(0),cnt(1){}
    phy(int weight_,int tall_):weight(weight_),tall(tall_),cnt(1){}
    void input(int weight_,int tall_);
    void show();
    void compared(phy p[],int n);
};

void phy::compared(phy p[],int n){
    for(int i=0; i<n; i++){
        if((weight < p[i].weight) && (tall < p[i].tall)){
            cnt++;
        }
    }
}

void phy::show(){
    cout << cnt << " ";
}

int main(){
    int n,w,t;
    cin >> n;
    phy* person;
    person = new phy[n];
    for(int i=0; i<n; i++){
        cin >> w >> t;
        person[i] = phy(w,t);
    }
    for(int i=0; i<n; i++){
        person[i].compared(person,n);
    }
    for(int i=0; i<n; i++){
        person[i].show();
    }
    delete[] person;
    return 0;
}

#include <iostream>
using namespace std;

int main(){
    int n,sum,value;
    cin >> n;
    for(int i=1; i<n; i++){
        sum = i;
        value = i;
        while(value){
            sum += value%10;
            value /= 10;
        }
        if(n == sum){
            cout << i;
            return 0;
        }
    }
    cout << "0";
    return 0;
}

#include <iostream>
using namespace std;

int main(){
    int card_num;
    int max_num = 0;
    int sum = 0, S_sum = 0;
    int arr[100]= {0,};
    cin >> card_num >> max_num;
    for(int i=0; i<card_num; i++){
        cin >> arr[i];
    }    
    for(int i=0; i<card_num-2; i++){
        for(int j=i+1; j<card_num-1; j++){
            for(int k=j+1; k<card_num; k++){
                sum = arr[i] + arr[j] + arr[k];
                if(sum <= max_num){
                    if(S_sum < sum){
                        S_sum = sum;
                    }
                }
            }
        }
    }

    cout << S_sum;
    return 0;
}

while 문을 사용하니 시간초과라고 뜬걸 보니 계산 문제이다.

낮에 올라가서 남은 높이, 밤에 내려간 것을 뺀 실제 올라간 높이 두 가지가 있다.

그러면 

남은 높이 / 올라간 높이

그리고 날짜는 1일부터 시작이므로

(V-A) / (A-B) + 1

이 식이 된다.

#include <iostream>
using namespace std;

int main(){
    int A,B,V;
    cin >> A >> B >> V;
    int res = 0;
    if((V-A)%(A-B) == 0) res = (V-A)/(A-B);
    else res = (V-A)/(A-B) + 1;
    cout << res+1;
    return 0;
}

#include <iostream>
using namespace std;
int main(){
    int n,tmp=1;
    cin >> n;
    
    int cnt = 1;
    while(1){
        tmp += (cnt-1)*6;
        if(tmp >= n) {
            cout << cnt;
            break;
        }
        else cnt++;
    }
    return 0;
}

N의 범위

1 -> 2 ~ 7 -> 8 ~ 19 -> 20 ~ 37 ...

그래서 끝번호를 비교해보면 1, 7, 19, 37 로 

x = x + ( i - 1) * 6 의 규칙을 가짐을 알 수 있다 ( i 는 1부터 증가하는 변수 )

#include <iostream>

using namespace std;

int main(){
    int x;
    int fix_cost; // 고정비용
    int cha_cost; // 가변비용
    int total_cost; // 총 비용
    cin >> fix_cost >> cha_cost >> total_cost;
    if((total_cost-cha_cost) == 0){
        cout << -1;
        return 0;
    }
    x = fix_cost / (total_cost-cha_cost) + 1;
    if(x < 0) cout << -1;
    else cout << x;

    return 0;
}

수식 : A + Bx < Cx

이를 x에 대해 정리하면,

A / (C-B) < x 이므로,

x 는 A/(C-B) + 1 이면된다

그리고 C-B 가 0일때는 -1를 출력하도록 하지않으면 런타임에러가 발생한다

#include <iostream>

using namespace std;

int main(){
    string s;
    int arr[26] = {3,3,3,4,4,4,5,5,5,6,6,6,7,7,7,8,8,8,8,9,9,9,10,10,10,10}; //다이얼에 해당하는 값을 미리 할당
    cin >> s;

    int sum = 0;

    for(int i=0; i<s.length(); i++){
        int index = s[i] - 65; //s에 -65 해줌으로써 arr의 index에 접근 (A가 아스키코드 65부터 시작함 ~ z는 122)
        sum += arr[index]; //arr에 있는 값을 더해줌
    }

    cout << sum;
    
    return 0;
}

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

int main(){
    string s1,s2;
    char p1[1000] = {0},p2[1000] = {0};

    cin >> s1 >> s2;
    int cnt1=0, cnt2 =0;
    for(int i=s1.length()-1; i >=0; i--){
        p1[cnt1++] = s1[i];
        p2[cnt2++] = s2[i];
    }

    int T1 = stoi(p1);
    int T2 = stoi(p2);

    if(T1 > T2) cout <<T1;
    else cout << T2;

    return 0;
}

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

int main(){
    string s;
    getline(cin,s);

    if(s.empty()){
        cout << 0;
        return 0;
    }

    int cnt = 1;

    for(int i=0; i<s.length(); i++){
        if(s[i] == ' '){
            cnt++;    
        }
    }
    if(s[0] == ' ') cnt--;
    if(s[s.length()-1] == ' ') cnt--;
    cout << cnt;
    return 0;
}

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

int main(){
    string s;    
    cin >> s;

    int a[26]={0,};
    int max = 0;
    int cnt;
    int index;

    transform(s.begin(),s.end(),s.begin(),::toupper);

    for(int i=0; i<s.length(); i++){
        a[s[i] - 'A']++;
    }

    for(int i=0; i<26; i++){
        if(max < a[i]){
            max = a[i];
            cnt = 0;
            index = i;
        }
        if(max == a[i]){
            cnt++;
        }
    }

    if(cnt > 1) cout << "?";
    else cout << (char)(index + 'A');
    
    return 0;
}

#include <iostream>
using namespace std;

int main(){
    int T,R,len;
    string s;
    cin >> T;
    for(int i=0; i<T; i++){
        cin >> R;
        cin >> s;
        for(int j = 0; j < s.length(); j++){
            for(int k = 0; k < R; k++){
                cout << s[j];
            }
        }
        cout << endl;
    }


}

#include <iostream>

using namespace std;

void show(string arr){
    string check = "abcdefghijklmnopqrstuvwxyz";
    for(int i=0; i < check.length(); i++){
            if(arr.find(check[i]) == string::npos) cout << -1 << " ";
            else{
                cout << arr.find(check[i]) << " ";
                continue;
            }
    }
}


int main(){
    string arr;

    cin >> arr;

    show(arr);

    return 0;
}

#include <iostream>
#define max 1000
using namespace std;

void cal(int n){
    int a,b,c,cnt=0;
    for(int i=100; i<=n; i++){
        a = i/100; //백의자리수
        b = (i%100)/10; //십의자리수
        c = (i%100)%10; //일의자리수
        if((a-b) == (b-c)) cnt++;
    }
    cout << 99+cnt << endl;
}

int main(){
    int n;
    cin >> n;

    if(n < 100) cout << n << endl;
    if(n > 99){
        cal(n);
    }
    return 0;
}

#include <iostream>
#include <cstdio>
#define max 10001

using namespace std;

bool arr[max];
int self(int n){
    int sum = n;

    while(1){
        if(n == 0) break;
        sum += n%10;    //한자리씩 더해줌
        n = n/10;   //한자리씩 없애줌
    }

    return sum;
}

int main(){

    for(int i=1; i<max; i++){
        int ind = self(i); // ind = 셀프넘버
        if(ind <= max){
            arr[ind] = true; // ind 가 arr의 인덱스로 들어가고 셀프넘버가 아니므로 true로 변경
        }
    }

    for(int i=1; i<max; i++){
        if(!arr[i]) cout << i << endl;
    }
    return 0;
}

#include <iostream>
#define max 1000
using namespace std;

void input(int n){
    float arr[max];
    
    for(int i=0; i<n; i++){
        double average = 0.0;
        int m,cnt=0;
        cin >> m;

        for(int j=0; j<m; j++){
            cin >> arr[j];
            average += arr[j];
        }
        average = average/m;
        
        for(int j=0; j<m; j++){
            if(arr[j] > average) cnt++;
        }
        cout<< fixed;
        cout.precision(3);
        cout << (double)cnt/m * 100.0 << "%" << endl;
    }
}

int main(){
    int n;
    cin >> n;

    input(n);

    return 0;
}

#include <iostream>

using namespace std;

void cal(int A,int B){
    int a = B/100;
    int b = (B-(a*100))/10;
    int c = B % 10;

    cout << A*c << endl;
    cout << A*b << endl;
    cout << A*a << endl;
    cout << A*B;
}

int main(){
    int A,B;

    cin >> A >> B;

    cal(A,B);

    return 0;
}

#include <iostream>

using namespace std;

void cal(int A,int B){
    cout << A+B << endl;
    cout << A-B << endl;
    cout << A*B << endl;
    cout << A/B << endl;
    cout << A%B << endl;
}

int main(){
    int A,B;
    cin >> A >> B;
    cal(A,B);
    return 0;
}

#include <iostream>
#include <algorithm>

#define MAX 1000

using namespace std;

class average{
    float n; //과목갯수
    float score[MAX]; //과목
    float M; //최고값
    float res; // 결과값

    public:
    average();
    void cal();
    void output();
};

average::average(){
    M = 0.0;
    res = 0.0;
}

void average::cal(){
    cin >> n;
    for(int i=0; i<n; i++){
        cin >> score[i];
        if(score[i] > M) M = score[i];
        res += score[i];
    }
    res = (res/M * 100.0) / n;
}

void average::output(){
    cout << res;
}

int main(){
    average student;

    student.cal();

    student.output();

    return 0;
}

너무 C만 쓰다보니까 최대한 C++ 스럽게 (?) 작성하려고 노력중이네요..