14929번: 귀찮아 (SIB) n과 xi가 주어짇나. n은 10만 이하ㅇ고, xi는 젗ㄹ댓값이 100이하인 정수디이다. www.acmicpc.net 문제 이해 각각의 두 원소끼리 곱한 합을 구하는 문제 즉, n=3이고 x1, x2, x3가 있으면 x1x2 + x1x3 + x2x3를 구하라는 문제이다. 해당 문제에선 규칙을 찾는게 중요 + 누적 합으로 계산 최적화 풀이 n=4일 때를 가정하면 아래와 같은 식을 얻을 수 있다. ex) n=4 { x1 x2 x3 x4 } x1x2 + x1x3 + x1x4 + x2x3 + x2x4 + x3x4 => x1(x2+x3+x4) + x2(x3+x4) + x3(x4) 규칙을 보면 x1부터 차례대로 자신을 제외한 다른 원소들의 합과 곱해지는 것을 볼 수 있다. 공통 인수..
4354번: 문자열 제곱 알파벳 소문자로 이루어진 두 문자열 a와 b가 주어졌을 때, a*b는 두 문자열을 이어붙이는 것을 뜻한다. 예를 들어, a="abc", b="def"일 때, a*b="abcdef"이다. 이러한 이어 붙이는 것을 곱셈으로 생각한다 www.acmicpc.net 문제 이해 & 기본 개념 s = a ^ n을 만족하는 최대의 n을 구해야하는 문제이므로, a의 길이가 가장 작은 경우를 찾아야하는 문제이다. 해당 문제는 kmp 알고리즘 중에서 최대 접두부 테이블을 이용하여 풀 수 있는데, 예시로 "ababab" 에 대한 최대 접두부 테이블은 아래와 같다. a b a b a b 0 0 1 2 3 4 테이블을 잘 보면 처음 ab에선 0 0이고 그 이후부턴 1 2 3 4로 계속 이어지는 것을 볼 ..
16197번: 두 동전 N×M 크기의 보드와 4개의 버튼으로 이루어진 게임이 있다. 보드는 1×1크기의 정사각형 칸으로 나누어져 있고, 각각의 칸은 비어있거나, 벽이다. 두 개의 빈 칸에는 동전이 하나씩 놓여져 있고, www.acmicpc.net 문제 이해 두 개의 동전 중 하나만을 떨어뜨리기 위해 눌러야하는 최소의 버튼 횟수를 구하는 문제였다. bfs를 사용하면 처음으로 동전 하나만 떨어지는 경우가 최소 횟수가 되므로, bfs를 선택 풀이 bfs를 사용하면 그리 어렵지 않게 풀 수 있는 문제인 것 같다. 큐 두 개로 동전 각각의 위치를 매번 갱신하면서 동전이 하나만 떨어지는지를 체크하면 된다 동전이 하나만 떨어지는 경우는 xor를 사용하면 간단히 체크할 수 있다. if(coin1Dropped xor c..
