전체 글171 백준 6062 / C++ https://www.acmicpc.net/problem/6062 6062번: Mixed Up Cows Each of Farmer John's N (4 2022. 7. 21. 백준 1520 / C++ https://www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net [ 풀이 ] dp[i][j]를 (i,j)부터 출발할때 끝점에 도착하는 것의 개수라고 하자. 기저조건은 dp[n-1][m-1]=1이다. dp[i][j]=∑ 4방향 dp[x][y] 이다. 4방향중 높이조건을 위배하거나 칸을 벗어난다면 제외해주면 된다. 답은 dp[0][0]이 된다. [ 코드 ] #include using namespace std; int dx[] = { -1,1,0,0 }; int dy[].. 2022. 7. 21. 백준 9251 / C++ https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net [ 풀이 ] dp[i][j]를 문자열 1개를 i번을 볼 것이고 , 나머지를 j번을 보려고 할 때 지금까지 겹치는 것의 개수라고 하자. 겹치지 않으면 한 문자열을 한칸 이동시켜준다. 겹치면 두 문자열을 모두 한칸 이동시켜준다. dp[i][j]=max(dp[i+1][j], dp[i][j+1], if a[i]=b[j], dp[i+1][j+1]+1) 로 쓸 수.. 2022. 7. 21. 백준 10942 / C++ https://www.acmicpc.net/problem/10942 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net [ 풀이 ] 어떤 문자열이 팰린드롬이라면 양쪽으로 1개씩 옮겨가면서 조사해줄 수 있다. 즉, 이전 상태를 다시 활용할 수 있으므로 메모이제이션이 가능한 문제다. dp[i][j]:= 구간[i,j]가 팰린드롬이면 1, 아니면 0을 의미한다고 하자. 이제 [i-1, j+1]로 이동한다면.. a[i-1]=a[j+1]이고 dp[i][j]=1일때만 dp[i-1][j+1]도 1이 된다. 비트연산으로 간단히 하면 dp[i-1][j+1]=dp[i][j.. 2022. 7. 21. 이전 1 ··· 37 38 39 40 41 42 43 다음