프로그래밍

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

[난이도] level3
[유형] 트리

[풀이]
칫솔 판매원(Leaf)부터 추천인을 거슬러 올라가면서 본인은 10%만큼, 추천인에게는 90%만큼 이익을 분배하면 됩니다.
전체 사람의 이름을 index로 매핑 시키면 쉽게 추천인을 찾을 수 있으므로 <String,Int> 타입의 맵을 선언하여
이름과 index를 매핑 하였습니다.

lateinit var answer:IntArray
lateinit var referral:Array<String>
var table = hashMapOf<String,Int>()
fun sol(name:String,v:Int){
    if(name=="-" || v==0) return
    var a = 0
    if(v%10!=0) a=1
    answer[table[name]!!]+=(0.9*v).toInt()+a
    sol(referral[table[name]!!],(0.1*v).toInt())
}
class Solution {
    fun solution(enroll: Array<String>, _referral: Array<String>, seller: Array<String>, amount: IntArray): IntArray {
        referral = _referral
        answer = IntArray(enroll.size)
        for(i in enroll.indices) table[enroll[i]]=i
        for(i in seller.indices) sol(seller[i],amount[i]*100)
        return answer
    }
}

https://github.com/has2/Problem-Solving/blob/master/programmers/level3/다단계_칫솔_판매.cpp

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

[난이도] level3
[유형] 구현

[풀이]
3차원 배열 map[202][202][2]를 선언하여
map[x][y][0] == true 이면 (x,y)~(x,y+1) 기둥이 설치된 것
map[x][y][1] == true 이면 (x,y)~(x+1,y) 보가 설치된 것
위와 같이 관리하도록 하였습니다.

이제 기둥과 보를 각각 설치할때 이것을 설치할 수 있는지와
제거할 때 제거할 수 있는지를 체크해야 합니다.

설치하는 할때 확인하는 것은 쉽습니다.
기둥의 경우 바닥인지, 아래 기둥이 있는지, 보가 있는지만 확인하면 설치가 가능하고
보의 경우 아래 기둥이 있는지, 양옆에 보가 있는지만 확인하면 됩니다.

하지만 제거할 때는 문제가 복잡해질 수도 있습니다.
특정 위치 (x,y)의 기둥이나 보를 제거한다고 할때,
"(x+b,y+b)에 기둥이나 보가 있으니까 (x,y)를 제거하면 안돼" 이렇게 생각하면 복잡해 지는 경우입니다.
단순하게
"(x,y)의 기둥(보) 를 지웠음에도 map의 모든 기둥과 보가 조건을 만족하고 있다면 (x,y)는 지워도 되겠네"
라고 생각하는 것이 좋습니다.

즉, (x,y)의 기둥(보)를 지워보고 nxn map의 모든 기둥봐 보를 2중 for문으로 체크해보면서 조건을 여전히 만족하는지를 체크하는 것입니다.

쿼리가 1000개이고 n이 최대 100이기 때문에 O(100x100x10000) 으로 충분히 시간내에 해결이 가능합니다.
만약 n이 좀더 큰수라면 지워야하는 (x,y)의 주변에 영향을 받을만한 (x+b,y+b)들만 체크해야 겠지만
n이 작아 생각할 필요가 없기 때문에 전체 점을 체크하였습니다.

(x,y) 위치의 기둥은 checkFunc[0](x,y), 보는 checkFunc[1](x,y) 로 체크할 수 있도록
lamda list를 만들었습니다 (0,1로 연결지을 수 있도록)

check 함수는 전체 점을 체크하는 함수입니다. 이곳에서 checkFunc를 사용하여 (x,y)를 제거했을 때 전체 점이
여전히 조건을 만족하면 true 아니면 false를 return합니다.

입력받은 x,y에 1씩 더하여 map을 +1,+1씩 평행이동 시켰다고 생각하고 풀면 index 범위 체크를 하지 않아도 됩니다.

var map = Array(202){Array(202){BooleanArray(2)}}
var checkFunc = listOf(
    {x:Int,y:Int -> y==1 || map[x][y-1][0] || map[x-1][y][1] || map[x][y][1]},
    {x:Int,y:Int -> (map[x-1][y][1] && map[x+1][y][1]) || map[x][y-1][0] || map[x+1][y-1][0] }
)
fun check(x:Int,y:Int,n:Int):Boolean{
    for(i in 1..n+1)
        for(j in 1..n+1){
            if(map[i][j][0] && !checkFunc[0](i,j)) return false
            if(map[i][j][1] && !checkFunc[1](i,j)) return false
        }
   return true
}
class Solution {
    fun solution(n: Int, build_frame: Array<IntArray>): Array<IntArray> {
        for((tx,ty,a,b) in build_frame){
            var x = tx+1
            var y = ty+1
            if(b==0){
                map[x][y][a]=false
                if(!check(x,y,n)) map[x][y][a]=true
            }else{
                if(checkFunc[a](x,y)) {
                    map[x][y][a]=true
                }
            }
        }
        var lst = mutableListOf<IntArray>()
        for(i in 1..n+1){
            for(j in 1..n+1){
                if(map[i][j][0]) lst.add(intArrayOf(i-1,j-1,0))
                if(map[i][j][1]) lst.add(intArrayOf(i-1,j-1,1))
            }
        }
        return lst.toTypedArray()
    }
}

https://github.com/has2/Problem-Solving/blob/master/programmers/level3/기둥과_보_설치.cpp

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

[난이도] level3
[유형] 플로이드 워셜

[풀이]

s에서 어떤 점 k(1~n)까지 같이 타고 갔다고 가정했을 때 요금의 최솟값은
s~k까지의 최단거리 + k~a의 최단거리 + k~b의 최단거리 입니다.
k를 1에서 n까지 바꿔보면서 최단거리를 모두 구해봤을 때의 최솟값이 정답입니다.
모든 점 (i,j)간의 최단거리를 구해야 하므로 플로이드 워셜 알고리즘을 이용하였습니다.

import java.lang.Integer.min
import java.util.*
const val inf = 20000001
var cost = Array(201){IntArray(201){inf} }
class Solution {
    fun solution(n: Int, s: Int, a: Int, b: Int, fares: Array<IntArray>): Int {
        var answer = inf
        for(v in fares){
            cost[v[0]][v[1]]=v[2]
            cost[v[1]][v[0]]=v[2]
        }
        for(i in 1..n) cost[i][i]=0

        for(k in 1..n){
            for(i in 1..n){
                for(j in 1..n){
                    if(cost[i][j] > cost[i][k]+cost[k][j]){
                        cost[i][j] = cost[i][k]+cost[k][j]
                        cost[j][i] = cost[i][j]
                    }
                }
            }
        }
        for(i in 1..n) answer = min(answer, cost[i][s] + cost[i][a] + cost[i][b])

        return answer
    }
}

https://github.com/has2/Problem-Solving/blob/master/programmers/level3/합승_택시_요금.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://programmers.co.kr/learn/courses/30/lessons/12924

[난이도] level2
[유형] 구현

[풀이]
n 1개로 무조건 n을 만들 수 있기 때문에 answer의 값은 1부터 시작합니다.
1~n-1을 순회하면서 i+(i+1)+(i+2)... 값을 만들어보면서 n이 넘어가면 break,
n이 나오면 answer에 1을 추가하고 break 하는식으로 답을 구해가면 됩니다.

n이 10000이고 i가 1인 경우에도
1+2+3+4.... = (n*(n+1))/2 = 10000 (등차수열 공식)
을 만족하려면 더하는 횟수인 n이 대충 계산해도 150도 넘을 수 없다는 것을 알 수 있습니다.
그러므로 시간복잡도는 O(10000*150) 정도로 시간내에 해결이 가능합니다.

#include <string>
#include <vector>
using namespace std;
int solution(int n) {
    int answer=1;
    for(int i=1;i<n;i++){ 
        bool ok=0;
        int sum=i,cur=i;
        while(sum<n){
            sum+=++cur;
            if(sum==n){
                answer++;
                break;
            }
        }
    }
    return answer;
}

https://github.com/has2/Problem-Solving/blob/master/programmers/level2/숫자의 표현.cpp

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

[난이도] level2
[유형] 분할정복

[풀이]
정사각형의 수가 모두 같지 않다면 4개로 분할된 정사각형을 다시 검사하도록
재귀함수를 호출해주고 모두 같다면 0,1인지에 따라 개수를 1개 더해줍니다.

#include <string>
#include <vector>
using namespace std;
vector<int> answer(2);
vector<vector<int>> arr;
int same(int y,int x,int n){
    int t = arr[y][x];
    for(int i=y;i<y+n;i++)
        for(int j=x;j<x+n;j++)
            if(t!=arr[i][j]) return -1;
    return t;
}
void sol(int y,int x,int n){
    int ret = same(y,x,n);
    if(ret!=-1){
        answer[ret]++;
        return;
    }    
    int b = n/2;
    sol(y,x,b);
    sol(y+b,x,b);
    sol(y,x+b,b);
    sol(y+b,x+b,b);
}

vector<int> solution(vector<vector<int>> _arr) {
    arr=_arr;
    sol(0,0,arr.size());
    return answer;
}

https://github.com/has2/Problem-Solving/blob/master/programmers/level2/쿼드압축 후 개수 세기.cpp

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

[난이도] level2
[유형] 구현

[풀이]
0의 개수를 직접 빼서 남은 1의 개수로
다음 string을 만들면서 1이 될때까지 반복하면 됩니다.

#include <string>
#include <vector>
#include <cmath>
#include <cstdio>
using namespace std;
using ll = long long;
vector<long long> solution(vector<long long> numbers) {
    vector<long long> answer;
    for(auto num : numbers){
        ll ret=0;
        int sz = log(num)/log(2)+2;
        if(num==0) sz=1;
        int idx;
        for(int i=0;i<sz;i++){
            if((num&(1LL<<i))==0) {
                idx=i;
                break;
            }
        }
        ret=num+(1LL<<(idx));
        if(idx>0) ret-=1LL<<(idx-1);
        answer.push_back(ret);
    }
    return answer;
}

https://github.com/has2/Problem-Solving/blob/master/programmers/level2/이진 변환 반복하기.cpp

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

[난이도] level2
[유형] 비트

[풀이]

1) 2진수로 표현했을 때 낮은 bit부터 확인하면서 0이 최초로 등장하는 index를 찾습니다.

2) 찾은 idx는 1로 바꿔주고 idx-1의 1은 0으로 바꿔주면 그 값이 조건을 만족하는 값입니다.
만약 0110 식으로 idx가 0이라면 0만 1로 바꿔주면 됩니다.

비트연산시 오버플로우가 날 수 있기 때문에 1LL<<idx와 같이 LL을 반드시 붙혀줘야 합니다.

#include <string>
#include <vector>
#include <cmath>
#include <cstdio>
using namespace std;
using ll = long long;
vector<long long> solution(vector<long long> numbers) {
    vector<long long> answer;
    for(auto num : numbers){
        ll ret=0;
        int sz = log(num)/log(2)+2;
        if(num==0) sz=1;
        int idx;
        for(int i=0;i<sz;i++){
            if((num&(1LL<<i))==0) {
                idx=i;
                break;
            }
        }
        ret=num+(1LL<<(idx));
        if(idx>0) ret-=1LL<<(idx-1);
        answer.push_back(ret);
    }
    return answer;
}

https://github.com/has2/Problem-Solving/blob/master/programmers/level2/2개 이하로 다른 비트.cpp