PS) 백준 2718, 2591, 2631, 2698번 (타일 채우기, 숫자카드, 줄 세우기, 인접한 비트의 개수) 골드 3으로 승급!
백준 2718 타일 채우기 음 ,, 어 바로 맞았네? (왜??.? 놀람요) 이전에 비슷한 타일 채우기 문제를 접해본 적 있었기 때문에, 이전과 비슷하게 풀었다. 뒤에서 추가될 수 있는 타일의 종류를 찾고, 더해주는 방식이다. 그러나 이렇게 문제가 복잡해지면 뒤에서 추가될 수 있는 타일의 종류가 많아지므로, 놓치는 타일이 있을 수 있어 비효율적이다. (야매임..) 조금 더 세분화된 dp를 이용해서 풀어보자!! #include long long dp[30]; int main() { int t; scanf("%d", &t); int n; dp[1] = 1; dp[2] = 5; int a; int b; for (int i = 3; i 1,1 이전에 연결지어 카드를 만든 경우와, 그렇지 않은 경우에 따라서 이후에..
2021. 5. 5.
PS) 백준 1958, 2225, 17069, 17070, 1655번 (LCS3, 합분해, 파이프 옮기기1, 2, 가운데를 말해요)
백준 1958번 LCS3 문자열 3개의 가장 긴 부분수열을 구하는 프로그램 문자열만 하나 많아졌을 뿐 구현하는 방법은 2개일때와 같음! dp[i][j][k] => 문자열 1의 i번째 문자, 문자열 2의 j번째 문자, 문자열 3의 k번째 문자까지 중에서 lcs의 길이 배열을 3차원으로 설정하고 구현해주면 됨. 모든 문자가 같은 경우 이전 문자열의 최장수열길이에서 1을 더해준것을 기록하고, 문자가 다른 경우 이전 탐색한 수열의 최댓값을 기록한다. #include #include #include #include using namespace std; int dp[105][105][105]; //문자열 3개의 LCS를 구하는 프로그램 int main() { string str1, str2, str3; cin >>..
2021. 5. 4.
PS) 백준 1309, 10164번 (동물원, 격자상의 경로)
오늘은 토요일이라 안하려 하다가 양심에 찔려서 몇문제라도 풀어본다.. 1309번 동물원 처음에 생각을 잘못해서,,,,,,,,, 삽질한 문제이다. 3차원 배열을 선언해서, i번째 열의, n행의 방의 동물의 여부에 따라서 계산을 해주었더니 구현이 되지 않았다. 깊게 생각하지 않고 가볍게 생각해보니 그렇게 어렵게 들어가지 않아도 되는 문제였다... i번째 열에서 올 수 있는 동물의 경우는 1) O 2) X 3) X X O X 이 세가지이다. 따라서 dp를 2차원으로 구현한다. dp[n][3] => n열에서 올 수 있는 경우는 세가지 경우 첫번째 경우는 이전 열에서 2,3번의 경우일 때 가능 두번째 경우는 이전 열에서 1,3번의 경우일 때 가능 세번째 경우는 이전 열에서 1,2,3번의 경우일 때 가능 그림으로 ..
2021. 5. 2.
PS) 백준 10844, 1965, 1946, 2854, 1563 (쉬운 계단 수, 상자 넣기, 신입 사원, 문제 출제, 개근상)
10844번 쉬운 계단 수 별로 안어려웠다. 하지만 한번 틀렸다. 그 이유는 정수 자료형 때문. [놓친점] 각 값을 계산해 줄 때 10억으로 나눈 나머지를 넣어주었기 때문에 자동적으로 10억 미만의 값이 나올 것이라고 착각했지만. dp[n][0] ~ dp[n][9]를 더한 값은 최대 100억이 되므로 long long자료형으로 변경해주어야 한다. 값이 커질 때, 최대 데이터를 확인하고 자료형을 체크하자! #include int dp[105][15]; //dp[n][i] => 길이가 n이고, i로 끝나는 계단수의 개수 int main() { int n; scanf("%d", &n); for (int i = 1; i
2021. 5. 1.
