여러가지 블로그

같은 배열들 사이가 줄로 연결되는것이기때문에 6 - 6 3-3 이런식으로 연결되는게 가장 이상적인조합이다 동일번호로 연결될시 최대한 많은 전깃줄을 연결할수있다 반대로 1-10 9-2 처럼 극단적으로 차이가 많이나는경우는 제거될 확률이 높아진다 그렇다면 많이 차이가 나는 경우를 지우면 될까? 아니다 반례가있다 전깃줄이 있다 서로 겹치는 상황이다 각 전깃줄마다 다른 전깃줄과 겹치는 부분을 모두 세본다 가장 많이 겹치는 순서대로 하나씩 지워본다 더이상 겹치는 전깃줄이 존재하지 않을때까지 이렇게 하는게 최고의 방법일까? 예제에서 각 전깃줄당 다른 전깃줄과 겹쳐지는 수를 구해보자 5 2 4 3 2 2 2 0 많이겹친 탑3를 제거하자 겹치는 전깃줄이 없어졌다 그리고 남은 전깃줄들의 숫자가 똑같았다 이것도 제거의 기..

카테고리 없음 2022. 8. 1. 13:58

링크 문제 이해하기 문제를 보자마자 저번에 풀었던 그 계단 건너기 문제가 떠올랐다 하지만 계단문제와다르다 계단문제는 모든 숫자를 다 건너가야하고, 맨끝 계단을 반드시 밟아야했다 이문제는 최대값이 되게 숫자를 집으라는것뿐 모든 숫자를 집으라는 말은 없었다 뭐 어차피 최대값을 나오게 하려면 대부분의 경우 모든 숫자를 다 집어야겠지만 그게 차이점이다 배열된 숫자들이 있고 거기서 고른 숫자가 최댓값이 되게 고른다 단. 연속으로 3숫자를 선택할수없다는 조건이 있다 입력 첫째줄에 포도주 잔의 개수 n이 주어짐 1 ≤ n ≤ 10,000 둘째줄부터 n+1줄까지 포도주잔안에 들어있는 포도주의 양이 순서대로 주어짐 포도주의 양은 음이 아닌 정수 출력 첫째줄에 최대로 마실수있는 포도주의 양을 출력 첫번째 아이디어 입력으로..

프로그래밍/백준풀이 2022. 7. 24. 22:27

문제링크 https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 각 층의 요소마다 최대값을 계산하는방식으로 구현을 해보아야할것같다 다만 n은 최대 500까지 나오고 그렇게되면 한층당 계산해야할 요소개수가 500개로 늘어나기때문에 조금 걸리긴하지만 시간제한은 넉넉한 편인것같으니 한번 구현해보았다 원트에 성공하였다 RGB거리와 같은방식으로 풀었다 핵심은 도착지점마다 계속 최대값을 구하고 갱신시켜 나가는것이다 이렇게 하면 이미 계산한 경로를 다시 되돌아가 풀지않아도 된다(동적계획법) # 정수 삼각형 import sys input..

프로그래밍/백준풀이 2022. 7. 18. 14:48

https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 푸는데 구현조차 하지못했다 4 1 6 2 1 3 100 1 108 10000 1 10000 RGB중에 최소값을 고르고(문명6고르고아님 ㅎ) 다음줄에서는 겹치지는 색깔중에 가장 작은것을 고른다 간단한 동적계획법이다 위의 예시를 보면 위와같은 방식은 틀린것을 알수있다 개선안으로 i최소값+ i색깔과 다른 i+1의 최소값과 i+1최소값 i+1색깔과 다른 i의 최소값과 비교 채택할시 ..

프로그래밍/백준풀이 2022. 7. 17. 18:54