프로그래밍

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

[난이도] Gold5
[유형] 수학

[풀이]
정육면체는 탁자위에서 보이는 정육면체의 면은 크게 3가지로 나눌 수 있습니다.
3면이 인접한 부분, 두 면이 인접한 부분, 한 면만 보이는 부분

1x1x1 짜리 주사위의 모양을 미리 알고 있으므로 위 3가지 모양의 최솟값을 미리 구해놓고
각각이 NxNxN 정육면체에 몇번 들어가는지를 구하면 됩니다.

3면이 인접한 부분, 두 면이 인접한 부분, 한 면만 보이는 부분의 최솟값을 각각
p,q,r이라고 하면

p는 정육면체의 맨 위의 꼭짓점 이므로 4*p ,
q는 탁자에 붙어있는 아래의 꼭짓점 4개와 탁자에 붙어있는 모서리를 제외한 8개의 모서리에
각각 N-2개만큼 존재하므로 4*q+8*(N-2)*q ,
r은 그 이외의 모든 면이므로 4*(N-2)*r+5*(N-2)*(N-2)*r

#include <cstdio>
#include <algorithm>
using namespace std;
using ll = long long;
ll N,a[6];
int main(){
    ll p=200,q=200,r=200;
    scanf("%lld",&N);
    for(int i=0;i<6;i++) {
        scanf("%lld",&a[i]);
        r=min(r,a[i]);
    }
    if(N==1) {
        int sum=0,m=0;
        for(int i=0;i<6;i++){
            sum+=a[i];
            m=max(m,(int)a[i]);
        }
        printf("%d",sum-m);
        return 0;
    }
    p=min(p,a[0]+a[1]+a[2]);
    p=min(p,a[0]+a[3]+a[4]);
    p=min(p,a[0]+a[1]+a[3]);
    p=min(p,a[0]+a[2]+a[4]);
    p=min(p,a[5]+a[3]+a[4]);
    p=min(p,a[5]+a[1]+a[3]);
    p=min(p,a[5]+a[1]+a[2]);
    p=min(p,a[5]+a[2]+a[4]);
    for(int i=0;i<6;i++){
        for(int j=0;j<6;j++){
            if(i!=j && i+j!=5) q=min(q,a[i]+a[j]);
        }
    }
    ll ans = 4*p+4*q+8*(N-2)*q+4*(N-2)*r+5*(N-2)*(N-2)*r;
    printf("%lld",ans);
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold5/1041.cpp

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

[난이도] Gold5
[유형] 수학

[풀이]
수열의 숫자들간의 관계를 그래프로 표현한 뒤, 모든 수에서 DFS를 돌려보면서
깊이가 N-1까지 도달했을 때, 즉 모든 수를 나누기3, 곱하기2 연산으로 방문을 완료했을 경우의 방문 순서를 출력해주면 됩니다.

예를 들어,
4 8 6 3 12 9
수열이 있을 경우
8을 만들려면 4 또는 24가 있어야 하는데 24는 수열에 없으므로
4->8 간선만 만들어주면 됩니다.
이런식으로 모든 수에 대해 어떤 수로부터 만들 수 있는지를 파악하여 간선을 만들어주면 됩니다.
숫자와 index를 매핑해주기 위해 map을 이용하였습니다.

#include <cstdio>
#include <vector>
#include <string>
#include <map>
using namespace std;
using ll = long long;
int N;
ll B[101];
map<ll,int> m;
vector<int> adj[101];
bool sol(int n,string s,int dep){
    if(dep==N-1){
        printf("%s",s.c_str());
        return true;
    }
    for(auto nxt : adj[n]) if(sol(nxt,s+" "+to_string(B[nxt]),dep+1)) return true;
    return false;
}
int main(){
    scanf("%d",&N);
    for(int i=0;i<N;i++) {
        scanf("%lld",&B[i]);
        m[B[i]]=i;
    }
    for(int i=0;i<N;i++){
        if(m.find(B[i]*3) != m.end()) adj[m[B[i]*3]].push_back(i);   
        if(B[i]%2==0 && m.find(B[i]/2) != m.end()) adj[m[B[i]/2]].push_back(i);
    }
    for(int i=0;i<N;i++) if(sol(i,to_string(B[i]),0)) return 0;
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold5/16936.cpp

https://programmers.co.kr/learn/courses/30/lessons/87390

[난이도] level2
[유형] 수학

[풀이]
n이 3일 때, 아래와 같이
1(1,1) 2(1,2) 3(1,3)
2(2,1) 2(2,2) 3(2,3)
3(3,1) 3(3,2) 3(3,3)

row,column 중 최댓값이 행렬의 값이 됩니다.
그러므로 left~right 값을 (row,column)의 좌표로 변환해주기만 하면
쉽게 답을 구할 수 있습니다.
left~right의 임의의 값 i에 대해 (row,column) 은 (row/n+1,row%mod+1) 이 됩니다.

#include <string>
#include <vector>
#include <cstdio>
#include <algorithm>
using namespace std;
using ll = long long;
vector<int> solution(int n, ll left, ll right) {
    vector<int> answer;
    for(ll i=left;i<=right;i++){
        answer.push_back(max(i/n,i%n)+1);
    }
    return answer;
}

https://github.com/has2/Problem-Solving/blob/master/programmers/level2/n^2_배열_자르기.cpp

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

[난이도] Gold3
[유형] 수학

[풀이]
골드바흐의 추측이라는 것을 알고 있어야 해결할 수 있는 문제입니다.

골드바흐의 추측은 2를 제외한 모든 짝수는 두개의 소수로 나타낼 수 있다는 것을 증명한 이론입니다.

즉 문제에서 A+B가 짝수이면서 2가 아니라면 무조건 YES를 출력하면 됩니다.

문제는 홀수인 경우인데, 홀수를 두개의 소수로 나누려면 한쪽은 무조건 짝수가 되어야 하는데

짝수인 소수는 2밖에 없으므로 소수 한개는 2로 확정됩니다.

그러므로 A+B-2 가 소수인지만 판별하면 되는데 이는 에라토스테네스의 체를 이용해

미리 2x10^6까지의 소수를 구해 놓음으로써 판별할 수 있습니다.

#include <cstdio>
#include <map>
#include <cmath>
#include <vector>
using namespace std;
using ll = long long;
int T;
ll A,B,np[2000001];
vector<ll> primes;
int main(){
    scanf("%d",&T);

    np[1]=1;
    for(int i=2;i<=2000000;i++){
        if(np[i]) continue;
        for(int j=i*2;j<=2000000;j+=i){
            np[j]=1;
        }
    }
    for(ll i=2;i<=2000000;i++) if(!np[i]) primes.push_back(i);

    while(T--){
        scanf("%lld%lld",&A,&B);
        ll sum = A+B;
        if(sum==2) {
            puts("NO");
            continue;
        }
        if(sum%2){
            sum-=2;
            bool ok=0;
            if(sum<=2000000) {
                puts(np[sum] ? "NO" : "YES");
                continue;
            }
            for(auto p : primes){
                if(sum<p) break;
                if(sum%p==0) {
                    ok=1;
                    break;
                }
            }
            puts(ok?"NO":"YES");
        }else{
            puts("YES");
        }
    }
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold3/15711.cpp

https://softeer.ai/practice/info.do?eventIdx=1&psProblemId=413&sw_prbl_sbms_sn=16837

[난이도] level2
[유형] 수학

[풀이]
규칙성을 찾는 문제입니다.
점화식을 만들어보면
A1 = 2 이며
Ak = 2*(Ak-1)+1 이 됩니다.

최종 답은 총 동그라미의 개수이므로 (An)^2을 출력해주면 됩니다.

#include <cstdio>
int N,ans=2;
int main(){
   scanf("%d",&N);
   while(N--) ans = 2*(ans-1)+1;
   printf("%d",ans*ans);
}

https://github.com/has2/Problem-Solving/blob/master/softeer/level2/지도_자동_구축.cpp

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

[난이도] Silver2
[유형] 수학

[풀이]
nCm 공식을 적용하여 분자, 분모를 각각 계산한 뒤 분자/분모를 해준것이 정답입니다.
n,m이 100 제한이라 unsigned long 범위도 넘어가므로 BigInteger를 이용해야 합니다.
C++같이 BigInteger를 지원하지 않는 경우에는 String을 통한 덧셈 연산으로 해결해야 합니다.

import java.io.BufferedReader
import java.io.InputStreamReader
import java.math.BigInteger
import java.util.*

fun main() = with(BufferedReader(InputStreamReader(System.`in`))){
    val (N,M) = readLine().split(' ').map{it.toInt()}
    var up = BigInteger("1")
    var down = BigInteger("1")
    for(i in 1..M){
        up = up.multiply(BigInteger((N-i+1).toString()))
        down = down.multiply(BigInteger(i.toString()))
    }
    println(up.divide(down))
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Silver2/2407.cpp

https://codeforces.com/contest/1549/problem/A

[난이도] Div.2
[유형] 수학

[풀이]
P가 소수일 때, P mod a=P mod b 를 만족하는 a,b를 찾는 문제입니다.
P가 소수이면 P-1은 반드시 1이외의 약수가 존재할 것이라는 생각으로
P-1의 약수를 찾는 O(루트N) 알고리즘을 적용하여
P-1의 약수중 가장 작은 수와 P-1을 출력해서 AC를 받았습니다.

컨테스트 종료 후 튜토리얼을 보니 P-1은 당연히 짝수이니 2와 P-1을 출력해주면 되는
훨씬 간단한 문제였습니다.

#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <iostream>
#include <map>
using namespace std;
using ll = long long;

int tc,P;

int sol(int p){

    for(int i=2;i<=sqrt(p);i++){
        if(p%i==0){
            return i;
        }
    }
    return 0;
}

int main(){
    scanf("%d",&tc);
    while(tc--){
        scanf("%d",&P);
        printf("%d %d\n",sol(P-1),P-1);
    }

}

https://github.com/has2/Problem-Solving/blob/master/codeforces/Round736-Div.2/A.cpp

https://codeforces.com/contest/1551/problem/A

[난이도] Div.3
[유형] 수학

[풀이]
1) N%3==0
정확히 1:2로 나눠지므로
답은 c1: N/3 c2 : N/3

2) N%3==1
1 burle만 추가로 필요하므로
답은 c1: (N/3)+1 c2 : (N/3)

3) N%3==2
2 burle만 추가로 필요하므로
답은 c1: (N/3) c2 : (N/3)+1

#include <cstdio>
using namespace std;
int tc,n,a,b;
int main(){
    scanf("%d",&tc);
    while(tc--){
        scanf("%d",&n);
        int k = n/3;
        int mod = n%3;

        a=b=k;
        if(mod==1){
            a++;
        }else if(mod==2){
            b++;
        }
        printf("%d %d\n",a,b);
    }
}

https://github.com/has2/Problem-Solving/blob/master/codeforces/Round734-Div.3/A.cpp