분류 전체보기

식보다는 관계가 중요했던 문제. 점화식을 세우는 것 보다는 현재값은 이전 값들의 합이라는 관계가 더 중요했던 문제다. n이 2보다 큰 상황에서, 1은 2,4에서 온다. 2는 1,3,5에서 온다. 3은 2,6에서 온다. 4는 1,5,7에서 온다. 5는 2,4,6,8에서 온다. 6은 3,5,9에서 온다. 7은 0,4,6에서 온다. 8은 5,7,9에서 온다. 9는 6,8에서 온다. 따라서 이전 값들의 합을 따로 저장했다가 더해서 현재값에 덧씌워 주면 된다. t = int(input()) for _ in range(t) : n = int(input()) num = [1 for x in range(10)] for _ in range(1,n) : n=num[:] num[0] = n[7] num[1] = n[2] +..

요약하면, 무게가 커지고, 선명도 값이 감소하는 최장수열을 구하라는 것 여타 다른 dp문제와 동일하되, 두가지 값을 동시에 비교한다. 반복문을 통해 0부터 n까지 기준값을 높히고, 0부터 x까지 비교값을 바꿔가며 무게와 서명도를 비교하고, 그에따라 compare 배열에 값을 바꿔준다. 출력은 compare의 최대값을 출력해주면 된다. t=int(input()) for _ in range(t): n=int(input()) compare=[1 for x in range(n)] w=[] c=[] for _ in range(n): a,b=map(float, input().split()) w.append(a) c.append(b) for x in range(n): for y in range(x): if w[x]>..

수를 1로 만드는 최소값을 구하되, 만드는 방법도 출력하라는 문제 간단하게 최소 방법은 3으로 나눠지면 3으로 나눈 dp값과 현재값을 비교해서 초기화, 2로 나눠지면 2로 나눈 dp값과 현재 값을 비교해서 초기화, 둘다 안되면 -1한 dp값과 현재 값을 비교해서 초기화. 문제는 방법이다. 나는 m이라는 2차원 리스트를 만들어서 dp값을 초기화 할때 그 값에 맞춰서 이전 경로를 추가하고, 이전 숫자를 추가하는 식으로 경로를 저장했다. 출력시에는 출력하는 숫자+m에 저장된 경로를 출력시켰다. n=int(input()) dp=[99999999 for x in range(n+4)] m=[[] for x in range(n+4)] dp[0],dp[1]=0,0 dp[2],dp[3]=1,1 m[0]=[0] m[1]=..

15988과 거의 유사한 문제, 다만 연속해서 사용할 수 없다는 것이 차이점이다. https://0422.tistory.com/71 15988 백준 파이썬 DP는 나열이 반이다. 잘 나열하는게 시작이다. 그럼 1부터 5정도까지만 나열해보자. 1 2 3 4 5 1 1+1 2 1+1+1 1+2 2+1 3 1+1+1+1 1+1+2 1+2+1 1+3 2+1+1 2+2 3+1 1+1+1+1+1 1+1+1+2 1+1+2+1 1+1+3 1+2+1+1 1+2+2.. 0422.tistory.com dp는 역시 나열이다. 1부터 6까지 나열해 보자. 1 2 3 4 5 6 1 2 1+2 2+1 3 1+2+1 1+3 3+1 1+3+1 2+1+2 2+3 3+2 1+2+1+2 1+2+3 1+3+2 2+1+2 2+1+3 2+3+1..

DP는 나열이 반이다. 잘 나열하는게 시작이다. 그럼 1부터 5정도까지만 나열해보자. 1 2 3 4 5 1 1+1 2 1+1+1 1+2 2+1 3 1+1+1+1 1+1+2 1+2+1 1+3 2+1+1 2+2 3+1 1+1+1+1+1 1+1+1+2 1+1+2+1 1+1+3 1+2+1+1 1+2+2 1+3+1 2+1+1+1 2+1+2 2+2+1 2+3 3+1+1 3+2 1개 2개 4개 7개 13개 이를 통해 알 수 있는 것은 어떤 수를 더하기로 나타낼 땐, 1,2,3을 각각 앞에 적고 +를 붙인 뒤에 오는 숫자들은 이전 수의 갯수와 동일하다는 것이다. 예를 들어 5의 경우, 1로 시작하는 경우는 1+ 뒤에 오는 모든 숫자들은 4의 경우와 똑같다. 2로 시작할때는 2+뒤에 오는 숫자들은 3의 경우와 똑같다. ..

캡틴 이다솜 문제를 고민하기에 앞서 사면체에 들어가는 대포알의 갯수를 고민해 보자. 1개, 4개, 10개, 20개... 다음은? 우선 밑면을 생각해 봤을때, 밑면에 추가되는 삼각형이 점점 커짐을 알 수 있다. n이 300,000이라고 해서 300,000까지 다 구해놓기에는 우리에게 주어진 자원은 한정적이므로, 다른 방식으로 구해보자. 결국 우리는 n보다 같거나 많은 양의 대포가 쌓여있는 사면체가 처음 등장하기까지 구해야 한다. 그러므로, 이렇게 세울 수 있다. n=int(input()) tri=[1,3] d=[1,4] idx=1 while n>d[-1]: idx+=1 tri.append(tri[idx-1]+(tri[idx-1]-tri[idx-2])+1) d.append(d[idx-1]+tri[idx]) ..

회문구조이면서 재귀구조를 가지는 팰린드롬 파티션의 갯수를 찾는 문제 예를들어 7은 7 1+5+1 2+3+2 1+1+3+1+1 3+1+3 1+1+1+1+1+1+1 은 되나, 1+2+1+2+1은 안된다. 1+2와 2+1이 재귀가 아니기 때문이다. 규칙을 찾아보자. 중간수를 기준으로 n을 나눠볼 수 있는데, 5와 6의 예시로 살펴보자. 5의 경우 6의 경우 1이 중간에 오는 경우, 1+1+1+1+1 2+1+22가 중간에 오는 경우, 없음 3이 중간에 오는 경우, 1+3+1 4가 중간에 오는 경우, 없음 5가 중간에 오는 경우 5 1이 중간에(?) 오는 경우, 1+1+1+1+1+1 2가 중간에 오는 경우, 2+2+2 1+1+2+1+1 3이 중간에(?) 오는 경우, 3+3 4가 중간에 오는 경우, 1+4+1 5가..

명확하게 정립되지 않고 경험적으로만 얻어졌던 부분들을 명쾌하게 정의해줘서 놀랐던 책이다. 나는 최근에 군대에서 전역했다. 군대 내부에는 아주 역겨운 유형의 인간들도 많았고, 배울 만한 점이 많은 사람들도 많았다. 수많은 유형의 인간들과 인간관계를 형성했다가 끊었다가 하며 경험적으로 정립한 부분들이 있는데, 요약하면 이렇다. 실패의 첫 단추는 기대이며, 무의식적인 기대가 모든 것을 망친다. 인간관계도 그렇다. 희생은 고결한 가치이며 우리의 인생은 모두 누군가의 희생으로 세워진 것이다. 놀랍게도 이 책은 경험으로 얻은 것들과 같은 맥락의 이야기를 하고 있었다. 1. 타인의 인정에 목매지 말고, 타인을 평가하지 마라. 타인의 과제와 내 과제를 명확하게 구분하고 수평적인 관계를 만들라. 타인의 인정에 목매어 자..

요약하면 n*m의 직사각형으로 이뤄진 연구소에 임의의 벽을 세개 세우고, 바이러스를 퍼뜨린다. 그리고 그 때의 안전공간(0)의 수를 출력하면 된다. 풀이: 1. dfs를 통해 벽을 세운다. 2. bfs를 통해 바이러스를 퍼뜨린다. 3. 0의 갯수를 센다. 치킨거리 문제와 다르게 실제로 벽을 세우고, 시뮬레이션을 돌려야 하기때문에 조금 더 오래 걸린다. https://0422.tistory.com/62 15686 백준 파이썬 치킨집을 m개만 남기되 집과 거리가 최소가 되도록 만드는 문제 m개 남기는 것은 dfs로, 거리 체크는 bfs로 할려고 했으나 시간초과. 이 놈의 dfs는 맨날 시간초과다. 아래는 처음 작성한 코드다. imp 0422.tistory.com 코드는 아래와 같다. import sys im..

정말 앞으로의 내 삶을 바꿀만한 책이었다. 거의 시험공부 하듯이 공부했다. 주변인들이 꼭 한 번 읽어봤으면 하는 책이다. 우리 오래오래 건강하게 살자. 나는 고기를 먹어도 항상 밥 한공기를 시켜서 같이 먹는 탄수화물 중독자였다. 아마 이런 식습관을 가지고 30대만 되어도 나는 당뇨의 위협에서 벗어나지 못했을 것이다. 푸아그라는 거위에게 탄수화물만 먹여서 지방간을 만든다음, 그 간을 조리해서 먹는 음식이다. 우리는 자기자신의 간을 푸아그라로 만들고 있다. 과도한 탄수화물은 지방의 축적을 늘리고(특히 지방과 같이 섭취했을때), 간에 지방이 쌓이게 만든다. 당은 모든 질병의 근원이다. 우리는 탄수화물 위주의 식단으로 설계된 생물이 아님에도 불구하고, 너무 많은 탄수화물을 섭취하고 있다. 우선적으로 당은 인슐린..