[백준 - 21134] Ant Typing
문제: https://www.acmicpc.net/problem/21134
인접한 두 수의 조합을 카운팅 해놓으면 어떤 배치에 대하여 거리를 쉽게 계산할 수 있다.
모든 배치의 경우의수는 9!이므로 모든 배치에 대해 거리를 계산해 보면 된다.
시작위치까지의 거리 계산을 해야하는 점에 주의해야한다.
[백준 - 21147] Triangular Collection
문제: https://www.acmicpc.net/problem/21147
한 변의 길이가 다른 두 변의 길이보다 작으면 삼각형을 만들 수 있다.
어떤 set에서 가장 낮은 두 값의 합이, 가장 큰 값의 합보다 크다면 그 set은 triangular 라고 할 수 있을 것이다.
n개의 숫자중 세 숫자를 골랐을 때 삼각형을 만들 수 있다면,
[2번째로 큰 수] ~ [제일 큰 수] 사이의 숫자들은 원하는대로 넣어도 된다.
따라서 삼각형을 만들 수 있는 세 숫자를 찾았으면, 2^(사이의 수) 만큼 정답에 더해주면 된다.
long long ans = 0;
for(int i=0;i<n;i++)
{
for(int j=i+1;j<n;j++)
{
for(int k=j+1;k<n;k++)
{
if(arr[k] < arr[i]+arr[j])
{
ans += (long long)1 << (k-j-1);
}
}
}
}1에 long long 캐스팅을 해주지 않아서 한번 틀렸다.
이런 부분을 주의해야겠다.
[백준 - 21138] Dominating Duos
문제: https://www.acmicpc.net/problem/21138
정렬+set을 이용하여 숫자가 높은 순서대로 뽑아서 set에 넣고 왼쪽이나 오른쪽에 원소가 존재할 때마다 카운트를 1 올렸다.
처음에는 카운트가 한번에 여러개 오를 줄 알고 이렇게 짰는데 양옆에 존재하는지 아닌지만 판단하면 된다는 것을 깨달았다.
그리고 permutation으로 주어지기 때문에 sort를 이용할 필요도 없었다.
sort를 빼니 1400ms -> 1200ms로 줄었다.
set과 upper_bound를 이용하지 않고 low와 high라는 변수만 가지고 갱신해서 푸니
거의 100ms까지 줄었다.
같은 시간 복잡도임에도 불구하고 set이 정렬에 비해 상당히 오래걸린다는 사실을 알게되었다.
