너와 나의 스토리

문제: https://www.acmicpc.net/problem/5557 문제 풀이: 주목할 조건 1. 중간 연산 결과가 [0, 20] 사이의 값이어야 한다. 2. 각 값은 [0, 9] 사이의 값이다. 3. 올바른 등식의 개수는 $2^63-1$ 이하이다. -> long long 사용해야 한다. dp[index][현재까지의 값]=경우의 수 로 dp를 만들고, 2중 포문으로 문제를 풀 수 있다. 소스 코드: 더보기 #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; int n,arr[102]; ll dp[102][21]; i..

문제: https://www.acmicpc.net/problem/11585 문제 풀이: 첫 번째 문자열을 a라고 하고, 찾아야 할 문자열을 b라고 하자. a는 원형이기 때문에 a가 [abcd]라면 [abcdabc]로 만들어 준다. 그리고 kmp로 고기 먹을 수 있는 경우의 수를 구하고, gcd를 구해 나눠준 후 출력한다. 하지만 이렇게 하면 a 배열 크기를 두 배로 사용한다. 메모리를 많이 사용하고 싶지 않다면 [소스 코드 2] 풀이처럼 풀 수도 있다. * gcd 함수에서, else문에서 return으로 안하고 바로 gcd 호출하도록 했더니 런타임 에러가 났다 ㅎㅎ 댕청- 소스 코드 1: 더보기 #include #include #include #include #include #include #includ..

문제: https://www.acmicpc.net/problem/1248 문제 풀이: 각 값들을 행렬로 표현하면 다음과 같다. 대각선은 자기 자신을 나타낸다. 즉, arr[idx][idx]의 부호는 $n_{idx}$의 부호이다. $n_{1}$ $n_{2}$ $n_{3}$ $n_{4}$ $n_{1}$ n1 n1+n2 n1+n2+n3 n1+n2+n3+n4 $n_{2}$ n2 n2+n3 n2+n3+n4 $n_{3}$ n3 n3+n4 $n_{4}$ n4 - 해당 숫자의 부호가 음수이면, 가능한 값은 [-10,1] - 해당 숫자의 부호가 양수이면, 가능한 값은 [1,10] - 해당 숫자의 부호가 0이면, 가능한 값은 '0' 이렇게 범위를 좁혀 문제를 풀 수 있다. 모든 경우의 수를 구하는 것이 아니라, 적당한 값..

문제: https://www.acmicpc.net/problem/9095 문제 풀이: n=3인 경우 3 = 1+1+1 = 1+2 = 2+1 = 3 이렇게 4가지 경우가 있다. n=4인 경우 4 = 3+1 -> [n=3]인 경우에 1씩 다 더하면 된다. = 2+2 -> [n=2]인 경우에 2씩 다 더하면 된다. = 1+3 -> [n=1]인 경우에 3씩 다 더하면 된다. 그럼 총 7가지 경우의 수가 나온다. 즉, dp[n]=dp[n-1]+dp[n-2]+dp[n-3] 으로 점화식을 세울 수 있다. 소스 코드: 더보기 #include #include #include #include #include #include #include using namespace std; int dp[13],n,tc; int main..

문제: https://www.acmicpc.net/problem/1987 문제 풀이: 그냥 간단한 DFS 문제이다.` TestCase: 2 4 CAAB ADEM => 6 소스 코드: 더보기 #include #include #include #include #include #include #include using namespace std; int n, m,res; char arr[22][22]; bool visit[22][22],exist[26]; int dx[4] = { 1,0,-1,0 }; int dy[4] = { 0,1,0,-1 }; void func(int x, int y, int cnt=1) { for (int i = 0; i < 4; i++) { int curx = x + dx[i]; int c..

문제: https://programmers.co.kr/learn/courses/30/lessons/60060 문제 풀이: 단순히 trie를 짠 다음에 queries[i]에서 '?'가 나오면 해당 trie 노드에서 갈라지는 모든 곳으로 가도록 구현했더니 효율성 테스트에서 시간 초과가 났다. -> 정적 트라이로 풀어도 ㅠㅠ 해설을 보니 words를 trie에 insert할 때, 원래 문자열들로 만드는 트라이 하나, 뒤집은 문자열로 만드는 트라이 하나, 이렇게 두 개 만들어 각각 넣어주면 된다고 한다. 그리고 문자열 길이마다 트라이를 미리 만들어 놓고, 길이에 맞는 트라이에 삽입함으로써 ?를 만났을 때 바로 가능한 문자들의 개수를 리턴해주고 끝나면 된다. 가능한 문자들의 개수는 처음 words를 입력할 때, ..

문제: https://programmers.co.kr/learn/courses/30/lessons/64062 문제 풀이: 건널 수 있는 "니니지 친구들"의 수를 binary search를 이용하여 구한다. binary search로 건널 사람의 수를 먼저 정한 후, 징검다리를 스캔하면서 (현재 징검다리 수 - 건넌 사람 수)가 0 미만인 연속된 징검다리의 수가 k개 이상이면 건널 사람 수를 줄이는 식으로 구현하면 된다. * 마지막 사람이 지난 후, 징검다리 숫자가 줄어드는 것이기 때문에, 지금 막 0이 된 경우는 건널 수 있는 것으로 판단한다. 소스 코드: int solution(vector stones, int k) { int answer = 0; int l = 0,r=200000000; while (..

문제: https://programmers.co.kr/learn/courses/30/lessons/60057 문제 풀이: 주목할 조건: 앞에서부터 반복되는 문자열이어야 한다. 반복되는 문자열의 길이가 같아야 한다. 반복되는 문자열의 길이가 [10,100) 사이의 숫자이면 길이가 2 증가하고 e.g. 11abc. -> 문자열 길이 5 풀이: 문자열의 길이를 1부터 n/2가지 늘려가면서 중복 문자열 개수를 카운트 최대한 길게 겹치는 문자는 절반씩 같은 문자 e.g. abcabc 맨 처음 문자열을 sub라고 두고, 다음부터 보는 문자열을 cnt로 둔다 같으면 cnt++ 아니면 지금까지 겹친 문자열 개수 계산한 다음 cnt=0으로 초기화 소스 코드: int solution(string s) { int len =..