[SWEA] D3 : 6190, 6057, 6019, 5986

[6190] : 정곤이의 단조 증가하는 수

• 입력 : N개의 정수 → 가능한 곱셈 조합을 알아보니까 계속 된 인덱싱이 필요하므로 벡터보다는 배열이 더 적합
• 출력 : 단조증가 수 중 가장 큰 곱셈조합 (없으면 -1)
• 전략
  • 단조 증가하는 수 판별 법 : 10으로 나누어보았을 때 직전 나머지가 현재 나머지보다 커야 함
  • 10보다 작은 수는 단조 증가로 판단하므로 do-while 사용

#include <iostream>

using namespace std;

bool isItIncreasingNum(int);

int main(void){
    int testCase;
    cin >> testCase;
    for(int tc = 1; tc < testCase + 1; tc++){
        int N;
        cin >> N;
        int *numArr = new int[N];
        for(int i = 0; i < N; i++)
            cin >> numArr[i];
        int mult, answer = -1;
        for(int i = 0; i < N - 1; i++){
            for(int j = i + 1; j < N; j++){
                mult = numArr[i] * numArr[j];
                if(isItIncreasingNum(mult))
                    if(mult > answer)
                        answer = mult;
            }
        }
        cout << "#" << tc << " " << answer << endl;;
    }
    
    return 0;
}

bool isItIncreasingNum(int num){
    bool isTrue = true;
    int prevMod = 10, currMod;
    do{
        currMod = num % 10;
        if(currMod > prevMod){
            isTrue = false;
            break;
        }
        prevMod = currMod;
        num /= 10;
    } while (num != 0);
    
    return isTrue;
}

[6057] : 그래프의 삼각형

• 입력 : 정점 개수, 간선 개수, 연결 된 좌표 번호 2개 → 대놓고 그래프 문제
• 출력 : 만들어지는 삼각형 갯수
• 전략
  • 삼각형 갯수 구하는 방법
  • 주어진 정점은 5개, 간선은 4개라고 가정을 해보자. 결론적으로 정점 1-2-5가 삼각형 1개를 이루고, 1-3이 연결된 선이 추가로 있다고 가정할 경우(그림 그려보세요) 이를 2d-array로 나타낸 표는 다음과 같을 것이다. (번호가 1로 시작하므로 arr[6][6]으로 만듬)

  • 	[0]	[1]	[2]	[3]	[4]	[5]
    [0]
    [1]			1	1		1
    [2]		1				1
    [3]		1
    [4]
    [5]		1	1

  • connectedSet 이라는 벡터는 row별로 몇 번째 column에 1이 들었는지를 찾고 그 인덱스를 push_back 한다. 점이 5개이므로 connectedSet은 5번 생성되고 제일 처음 생성된 connectedSet에 들어가있는 인덱스는 2, 3, 5이다. 즉, 1번 점이 2번, 3번, 5번 점과 연결 되어있으므로 2번-3번 / 2번-5번 / 3번-5번 점이 혹시 연결되어있다면 하나의 삼각형이 생기는 것이다.

#include <iostream>
#include <vector>

using namespace std;

int graph[51][51];

int countTriangle(vector<int> v);
int main(void){
    int testCase, vertex, edge;
    cin >> testCase;
    for(int tc = 1; tc <= testCase; tc++){
        // initialize graph
        for(int i = 0; i < 51; i++)
            for(int j = 0; j < 51; j++)
                graph[i][j] = 0;
        
        cin >> vertex >> edge;
        for(int e = 0; e < edge; e++){
            int x, y;
            cin >> x >> y;
            graph[x][y] = graph[y][x] = 1;
        }
        
        vector<int> connectedSet;
        int sum = 0;
        for(int v1 = 1; v1 <= vertex - 2; v1++){
            for(int v2 = v1 + 1; v2 <= vertex; v2++){
                if(graph[v1][v2] == 1){
                    connectedSet.push_back(v2);
                }
            }
            sum += countTriangle(connectedSet);
            connectedSet.clear();
        }
        cout << "#" << tc << " " << sum << endl;
    }
    
    return 0;
}

int countTriangle(vector<int> v){
    int cnt = 0, v_size = v.size();
    for(int i = 0; i < v_size - 1; i++){
        for(int j = i + 1; j < v_size; j++){
            int x = v.at(i), y = v.at(j);
            if(graph[x][y] == 1) cnt++;
        }
    }    
    return cnt;
}

[6019] : 기차 사이의 파리

• 입력 : 기차 사이의 거리, 두 기차의 속도, 파리의 속도 → 대놓고 수학 문제...;;; 사람들 한테 물어보면서 무한급수 다시 찾아봤잖아;;;;(special thanks to Brad & Steve)
• 출력 : 두 기차가 충돌할 때 까지 파리가 움직인 거리
• 전략
  • 무한 급수 문제를 풀 수 있는가? 예 - 푸세요 / 아니오 - 몇 문제 보고 오세요
  • 파리가 A기차에서 B기차로 갈 떄와 B기차에서 A기차로 움직일 때는 다르니까 초항이 2개!
  • (a1 + a2) / (1 - r) 새록새록 ~

#include <iostream>
#include <iomanip>

using namespace std;

int main(void){
    int testCase;
    cin >> testCase;
    for(int tc = 1; tc <= testCase; tc++){
        double D, Va, Vb, Vf;
        cin >> D >> Va >> Vb >> Vf;
        double a1, a2, r;
        a1 = Vf * D / (Vf + Vb);
        a2 = Vf * D * (Vf - Va) / ((Vf + Va) * (Vf + Vb));
        r = (Vf - Va) * (Vf - Vb) / ((Vf + Va) * (Vf + Vb));
        cout << fixed << setprecision(6) << "#" << tc << " " << (a1 + a2) / (1 - r) << endl;
    }
    return 0;
}

[5986] : 새샘이와 세 소수

• 입력 : 홀수인 하나의 정수
• 출력 : 세 소수의 합으로 나타낼 수 있는 경우의 수
• 전략
  • 귀찮으니까 일단 소수 목록을 구해 놓는다(결국 이렇게 하는 게 맞나봄 밑에 댓글에 나와있더라고.. 담부턴 댓부터 읽을래ㅎㅎ)
  • 구하고 보니 소수의 개수는 168개이고, 세 소수의 합으로 홀수를 표현하니 뭐 3중 for문 돌려도 괜찮겠지

 

#include <iostream>

using namespace std;

int primeNumbers[168], sumSet[999], testCase;

void getPrimeNumbers();
int countCases(int, int);

int main(void){
    getPrimeNumbers();
    cin >> testCase;
    for(int tc = 1; tc <= testCase; tc++){
        int N;
        cin >> N;
        // get array position of num N
        int pos;
        for(pos = 0; pos < 168; pos++){
            if(primeNumbers[pos] > N)
                break;
        }
        cout << "#" << tc << " " << countCases(N, pos) << endl;
    }
    return 0;
}

void getPrimeNumbers(void){
    int arr[1000]; // 168이라는 크기는 소수가 몇개인지 구해본 것
    for(int i = 0; i < 1000; i++)
        arr[i] = 0;
    for(int i = 2; i < 1000; i++){
        if(arr[i] > 0)
            continue;
        arr[i]++;
        for(int mult = 2; mult <= 1000 / i; mult++)
            arr[mult * i]--;
    }
    int pos = 0;
    for(int i = 2; i < 1000; i++){
        if(arr[i] == 1)
            primeNumbers[pos++] = i;
    }
    
}

int countCases(int N, int pos){
    int cnt = 0, sum = 0;
    for(int x = 0; x < pos; x++){
        for(int y = x; y < pos; y++){
            for(int z = y; z < pos; z++){
                sum = primeNumbers[x] + primeNumbers[y] + primeNumbers[z];
                if(sum > N) break;
                if(sum != N) continue;
                cnt++;
            }
        }
    }
    return cnt;
}