[백준] 2565번 전깃줄 (C)

문제 출처 한국정보올림피아드 지역본선 2007 초등부 4번 문제 주소 백준 2565번 전깃줄 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 위치의 번호가 차례로 주어진다. 위치의 번호는 500 이하의 자연수이고, 같은 위치에 두 개 이상의 전깃줄이 연결될 수 없다. www.acmicpc.net 알고리즘 DP 힌트 서로 교차하지 않는 전깃줄의 최대 개수를 구한다. 문제풀이 서로 교차하지 않는 전깃줄의 최대 개수를 구하기 위해선 한 쪽 전봇대 기준으로 정렬을 한 뒤 나머지 전봇대의 번호에서 가장 긴 증가하는 수열을 구하면 된다. #include ..

• format_list_bulleted Problem Solve/Dynamic Programming
• · 2020. 4. 12.
• textsms

[백준] 11054번 가장 긴 바이토닉 부분 수열 (C)

문제 주소 백준 11054번 가장 긴 바이토닉 부분 수열 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 알고리즘 DP 힌트 i위치까지 가장 긴 증가하는 부분수열의 길이와 i위치까지 가장 긴 감소하는 부분 수열의 길이를 구한다. 문제풀이 dp[i][0]에 i위치까지 가장 긴 증가하는 부분수열의 길이 dp[i][1]에 i위치까지 가장 긴 감소하는 부분 수열의 길이를 저장하고 두 합이 가장 큰 것의 값을 구한다. #include using namespace std; int in[1002]; int dp[1002][2]; int mai..

• format_list_bulleted Problem Solve/Dynamic Programming
• · 2020. 4. 9.
• textsms

[백준] 11053번 가장 긴 증가하는 부분 수열 (C)

문제 주소 백준 11053번 가장 긴 증가하는 부분 수열 불러오는 중입니다... 알고리즘 DP 힌트 dp배열에 i번째 수 까지 가장 긴 증가하는 부분 수열의 길이를 저장한다. 문제풀이 i번째 수 까지 가장 긴 증가하는 부분 수열의 길이를 구하기 위해선 i번째 이하의 1~i-1의 구간의 수를 j라 할 때 in[i]가 in[j]보다 크다면 dp[j]+1, 작다면 dp[j]를 선택한 값의 최대값을 구하면 된다. 답은 dp[1]~dp[n]까지의 수 중 최대값이다. #include using namespace std; int dp[1001]; int in[1001]; int main(){ int n; cin>>n; for(int i=1;i>in[i]; int ans=0; for(int i=1;i

• format_list_bulleted Problem Solve/Dynamic Programming
• · 2020. 4. 6.
• textsms

[Python] 하노이 탑 경로, 이동 횟수 구하기

하노이 탑의 경로와 이동 횟수를 알기 위해선 시작점과 끝점 뿐만 아니라 어디를 거쳐서 이동하는지도 고려해야한다. n번 원판이 가장 아래 있기 때문에 이 원판을 옮기기 위해선 그 위에 있는 n-1개의 원판을 다른 곳으로 이동 시켜야 한다. 시작 : a(파이썬에서 from 이미 모듈을 가져오는데 사용되므로 a로 변수명을 정하였다.) 거쳐가는 곳 : by 끝: to 알고리즘은 다음과 같다. n-1개의 원판을 by에 옮긴다. n번째 원판을 to로 옮긴다. by에 있는 n-1개의 원판을 to로 옮긴다. 이 알고리즘을 바탕으로 다음과 같이 코드를 작성해 볼 수 있다. def hanoi (a ,by,to,n): if n==1: print("1: "+a+" --> "+to) return 1 ans=0 ans+=hano..

• format_list_bulleted Python
• · 2020. 4. 1.
• textsms

[백준] 2156번 포도주 시식 (C)

문제 주소 백준 2156번 포도주 시식 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규칙이 있다. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다. 연속으로 놓여 있는 3잔을 모두 마실 수는 없다. 효주는 될 수 있는 대로 많은 양의 포도주를 맛보기 위해서 어떤 포도주 잔을 선택해야 할지 고 www.acmicpc.net 알고리즘 DP 힌트 dp배열에 그날 포도주를 마셨을 때와 마시지 않았을 때의 최대값을 저장한다. 문제풀이 dp[i][0], dp[i][1]은 각각 i번째까지의 ..

• format_list_bulleted Problem Solve/Dynamic Programming
• · 2020. 3. 30.
• textsms

[백준] 10844번 쉬운 계산 수 (C)

문제 주소 백준 10844번 쉬운 계산 수 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 알고리즘 DP 힌트 dp배열에 i자리수중 j로 끝나는 수의 개수를 저장한다. 문제풀이 dp배열에 i자리 수중 j로 끝나는 수의 개수를 dp[i][j]에 저장한다. 0으로 끝나는 경우와 9로 끝나는 경우 그 이전의 수가 될 수 있는 수는 1과 8밖에 없기 때문에 따로 처리해준다. #include using namespace std; int dp[101][10]; int main(){ int n; cin>>n; //초기항 설정 for(int i=1;i

• format_list_bulleted Problem Solve/Dynamic Programming
• · 2020. 3. 30.
• textsms