본문 바로가기

Algorithm159

#1012 유기농 배추 # 문제 # 입력 및 출력 # 풀이 dfs로 풀면 될 것 같았다 가로 세로가 좀 헷갈렸다ㅋㅋ 배열 접근할 때 인덱스와 가로세로가 반대여서 그거 생각한다고 좀 걸린 것 같다 #include using namespace std; int visit[52][52]; int field[52][52]; int dx[4] = { 0,-1,0,1 }; int dy[4] = { -1,0,1,0 }; int T, X, Y, K; void clear() { // 배열 초기화 for (int i = 1; i < 51; i++) { for (int j = 1; j < 51; j++) { visit[i][j] = 0; field[i][j] = 0; } } } void dfs(int x,int y) { visit[x][y] = 1.. 2022. 6. 11.
#11727 2xn 타일링 2 # 문제 # 입력 및 출력 # 풀이 저번에 풀었던 문제에서 조금 추가된 문제다 2x1 타일 한개로 끝나는 경우는 dp[n-1]가지 1x2 타일 두개로 끝나는 경우는 dp[n-2]가지 2x2 타일 한개로 끝나는 경우는 dp[n-2]가지가 됨 따라서 점화식은 dp[i] = dp[i-1] + dp[i-2] * 2가 됨 #include using namespace std; int dp[1001]; int main() { int n; cin >> n; dp[1] = 1, dp[2] = 3; for (int i = 3; i 2022. 6. 11.
#9934 완전 이진 트리 # 문제 # 입력 및 출력 # 풀이 빌딩 방문 방법은 어떤 트리를 중위순회하는 방법이다 가운데에 있는 숫자가 루트 노드가 된다 처음에 작성한 코드가 아래와 같음 #include using namespace std; int b[1024]; int k, m = 1; void print(int n) { if (n == 0) return; int tmp = n / 2; while (tmp b[i]; print(m - 1); } 이렇게 해도 정답은 되지만 알아보기가 좀 힘들다고 생각했음 그래서 다른 사람 코드도 찾아봤다 다른 사람들은 시작점과 끝점을 매개변수로 받아서 중간값을 계산하고 중간값을 기준으로 왼쪽 자식 노드와 오른쪽 자식 .. 2022. 6. 10.
#10844 쉬운 계단 수 # 문제 # 입력 및 출력 # 풀이 이 문제만 한 3일은 본 것 같다 구글링 안하고 내 힘으로 풀고 싶어서 매일 매일 들여다봤음ㅋㅋㅋ 진짜 도저히 모르겠더라 처음에 생각한 방법이 모든 숫자는 2개씩 숫자를 만들 수 있으니까 예외인 0, 9 갯수를 찾으려고 했다 도저히 규칙을 모르겠어서 포기했음 구글에서 dp문제 찾아보다가 경우의 수를 가져온다는 말을 보고 바로 생각해냈다 계속 1차원 dp문제만 풀다 보니까 2차원으로 푸는건 완전 잊고 있었음 점화식이 dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1]이 된다 (단, 0 < j < 9) 0일땐 dp[i][0] = dp[i-1][1] 9일땐 dp[i][9] = dp[i-1][8] 왜냐하면 0이 가장 뒤에 오려면 바로 앞의 숫자는 1밖에 못오.. 2022. 6. 9.
#11726 2xn 타일링 # 문제 # 입력 및 출력 # 풀이 예전에 푸는 방법은 찾았는데 이해를 못해서 그냥 북마크 해두고 나중에 이해될때 다시 풀려고 했다 전에 01타일 문제를 풀다가 이문제와 내용이 비슷해서 이제는 이해될 것 같아서 다시 풀어봤다 n>=3 일때 항상 타일은 ㅣ타일 한개와 ㅡㅡ 타일 두개로 끝남 따라서 2xn 타일링 방법은 총 두가지임 1) n-1 타일링 방법에 l 타일을 더하는 방법 2) n-2 타일링 방법에 ㅡㅡ 타일을 더하는 방법 따라서 점화식은 dp[n] = dp[n-1] + dp[n-2]가 됨 #include using namespace std; int dp[1001]; int main() { int n; cin >> n; dp[1] = 1, dp[2] = 2; for (int i = 3; i 2022. 6. 9.
#15650 N과 M (2) # 문제 # 입력 및 출력 # 풀이 앞의 #15649 N과 M (1)문제에서 조금 변형된 문제다 앞의 문제와 기본적인 조건은 동일하나 오름차순 수열만 출력하도록 했다 처음엔 n==0일때 visit를 관리하면 될 줄 알았는데 그건 상관없는 내용이었고 그냥 dfs인자로 현재 반복문 인덱스를 넘겨주면 됨 그럼 n+1일때 반복문은 n일때보다 더 큰값만 조회하게 됨 #include #include using namespace std; vector p; int visit[9]; int N, M; void print() { for (int i = 0; i < p.size(); i++) { cout M; dfs(0, 0); } 간단한 내용인데 은근 오래 걸렸다ㅋㅋ 2022. 6. 8.

티스토리툴바