13458 시험 감독
2302 극장 좌석
2842 집배원 한상덕
4781 사탕 가게
2131 로봇 명령
2098 외판원 순회
1016 제곱ㄴㄴ수
11066 파일 합치기
12206 Seven-segment Display(Small)
1495 기타리스트
2352 반도체 설계
1237 정ㅋ벅ㅋ
1026 보물
1009 분산처리
4883 삼각 그래프
1102 발전소
2228 구간 나누기
3026 V
2159 케익 배달
1415 사탕
2629 양팔 저울
10835 카드게임
2665 미로만들기
1373 2진수 8진수
1103 게임
1398 동전 문제
4948 베르트랑 공준
10802 369 게임
1315 RPG
12851 숨바꼭질 2
1039 교환
13458
방마다 총감독관 1명 + 부감독관 +a계산해서 합하면 된다.
2302
n개의 연속된 자리가 있을 때 가능한 경우의 수는 피보나치 수열과 같다. vip좌석으로 나누어져 있으면 서로가 서로에게 독립적이므로 vip좌석을 *로 생각하면 된다.
2842
높이를 모두 vector에 받아서 sort한 후 1<=i<=j<=n*n인 i,j에 대해 v[i]~v[j] 사이에서 K,P가 모두 check되는지 확인하고 된다면 i++, 안되면 j++. i의 최대값은 min(min(a(K)), a(P))이고 j의 최소값은 max(max(a(K)),a(P))이므로 1<=i<=left_max, right_min<=j<=n*n까지 줄어든다. 이때 탐색시간은 O(left_max+n*n-right_min)이고 괜히 저 범위에 이분탐색을 적용하면 안풀리거나 시간이 오히려 늘어난다. 실제 더블포인터 사용시 72MS, 한쪽에 이분탐색을 사용시 700MS가 걸렸다.
4781
동전문제와 같다. 소수점 계산하기 귀찮으므로 문자열로 계산했다.
2131
신형 로봇은 방향전환에 cost가 없다. 지뢰에서 1칸 떨어진곳에서만 scan이 가능하므로
d[i][j] : i번째 지뢰의 j번방향으로 접근할 때 필요한 최소명령의 수
를 생각하과 bottom-up방식으로 처리한다. 명령수 = 점 두개를 있는 선분의 개수와 동일하다. scan cnt는 끝나고 ans+=지뢰 개수 하면 편하다.
2098
도시가 2~16개밖에 안되기 때문에 bitmask로 표시하고 dfs를 돌려서 min값을 뽑으면 된다.
1016
https://github.com/kdk8361/BOJ/blob/master/Math/1016.cpp
11066
구간합+dp
12206
ERROR를 표시하는 조건이
1. 다음 순서가 명확하지 않을 때
2. 출력 상태가 명확하지 않을 때
이것만 조심하고 reliable bit를 잘 처리하면 된다.
https://github.com/kdk8361/BOJ/blob/master/12206.cpp
1495
https://github.com/kdk8361/BOJ/blob/master/dp/1495.cpp
2352
LIS를 이용한다.
1237
문제를 잘 읽자
1026
A를 마음대로 재배열 가능하다 => A,B 재배열하는것과 다름이 없다. 오름차순, 내림차순 정렬하고 연산하면된다.
1009
컴퓨터가 10대다. 1의 자리에 영향을 미치는건 1의 자리 수 뿐이다. 0~9는 모두 제곱을 계속 할 경우 주기가 있으므로 그것을 이용하면 손쉽게 구할 수 있다.
https://github.com/kdk8361/BOJ/blob/master/1009.cpp
4883
그래프에서 화살표를 잘 보자
https://github.com/kdk8361/BOJ/blob/master/dp/4883.cpp
1102
가동중인 발전기에서만 다른 발전기를 가동시킬 수 있다는 점과 가동중인 발전소를 bitmask로 표현이 가능하다는 점을 이용한다.
https://github.com/kdk8361/BOJ/blob/master/dp/1102.cpp
2228
dp 조건을 잘 생각해보자.
3026
다시 풀어볼 예정.
2159
2131번과 비슷하다. 단순 최단거리만 계속 계산하면 된다.
1415
동전문제의 활용. 가격이 <=10000까지고 개수가 50개이므로 50만까지 소수를 모두 구해놓고 해결한다.
2629
x번째 추를 더하거나 빼거나 사용하지 않거나 세가지 경우 dp
https://github.com/kdk8361/BOJ/blob/master/dp/2629.cpp
10835
https://github.com/kdk8361/BOJ/blob/master/dp/10835.cpp
2665
단순 bfs
https://github.com/kdk8361/BOJ/blob/master/bfs/2665.cpp
1373
string으로 받고 3비트씩 끊어서 계산하면된다.
1103
https://github.com/kdk8361/BOJ/blob/master/dp/1103.cpp
1398
https://github.com/kdk8361/BOJ/blob/master/greedy/1398.cpp
4948
에라토스테네스의 체. 소수판별.
10802
설명이 어렵다..
https://github.com/kdk8361/BOJ/blob/master/dp/10802.cpp
1315
i,j에 도달할 수 있다는 걸 판별하는게 중요한 것 같다.
https://github.com/kdk8361/BOJ/blob/master/dp/1315.cpp
12851
하... 다풀어놓고 n==k에서 0\n1이 아니라 0\n만 출력해서 6번을 삽질했다. 문제를 잘 읽자.
https://github.com/kdk8361/BOJ/blob/master/bfs/12851.cpp
1039
길이가 1이면 만족하는 i,j가 없으로 k번 연산을 할 수 없기 때문에 -1
길이가 2이고 1의 자리가 0이면 교환 자체는 가능하지만 첫자리가 0이면 안된다는 조건을 위배하므로 -1
길이가 3이상이라도 첫번째 자리와 다른자리의 0을 교환하면 안된다.
이 점만 잘 지켜주면 bfs로 무난히 풀린다.