전체 글 썸네일형 리스트형 BOJ)1576 DNA점수 문제: icpc.me/1576 점수판을 채우는 규칙이 주어질 때 주어진 DNA 문자열의 각 문자열에서 얻을 수 있는 점수의 평균의 최댓값을 구하는 문제이다. 우리는 평균의 최댓값을 구하기 위해서 총점의 최댓값을 구하면 된다. 결국 총점이 최대가 되도록 점수판을 채우면 되는것이다. 우리는 다이나믹 프로그래밍을 이용해서 총점이 최대가 되도록 점수판을 채워나갈 것이다. 점수판을 채우는 순서는 임의로 지정해 줄 수 있다. dp테이블은 dp[4][4][10*16*2] 이 될것이다. dp 테이블이 의미하는 바는 dp[x][y][z]일때 (x,y)까지 채웠고 점수판의 점수 총합이 z일 때 총점의 최댓값으로 정의하면 된다. 우리는 점수판의 총점이 음수가 될 때도 있으니 그걸 고려하여 10*16의 총점에 2를 곱해주었다.. 더보기 BOJ)10265 MT 문제: icpc.me/10265 K이하의 사람이 버스에 탈 수 있을 때 버스에 탈 수 있는 최대 인원을 출력하는 문제이다. 문제에는 조건이 있는데 A라는 사람은 B라는 사람이 버스에 안타면 A도 반드시 안타는 정보 N개가 주어진다. 우리는 이러한 조건을 B->A라는 방향 그래프로 만들어 준 SCC끼리 분류를 한다음 다음 위상 정렬을 이용하여 X라는 정점이 방문 가능한 모든점 Y는 반드시 X의 인원을 포함한다고 정의 가능하다. 이 때 X의 인원은 SCC의 그룹 크기와 동치가 된다. 따라서 연결 그래프마다 최소 인원~최대 인원 셋을 저장한 뒤 Knapsack문제를 해결하듯이 다이나믹 프로그래밍을 이용해주어 답을 계산해주면 된다. 이때 연결 그래프의 수는 SCC 그래프의 indegree가 0인 SCC의 개수이.. 더보기 BOJ)3977 축구 전술 문제: icpc.me/3977 A->B로 이동해야하는 전술들이 주어질 때 시작 지점이 될 수 있는 위치를 찾는 문제이다. 이 때 적절한 시작지점이 없으면 Confused를 출력하면 된다. 여기서 SCC를 이루는 그룹이면 어떤 곳에서 시작하던 topology에 의해 나머지 지점들을 전부 탐색 가능하니 정점들을 SCC로 묶은 뒤 indegree가 0인 지점이 하나일 때는 해당 SCC에 속하는 모든 점들이 시작지점이 될 수 있고, 만약 indegree가 0인 지점이 여러곳일 경우에는 어떤 지점에서 시작해도 모든 점을 방문 불가능하기 때문에 Confused를 출력해주면 된다. 1234567891011121314151617181920212223242526272829303132333435363738394041424.. 더보기 이전 1 ··· 86 87 88 89 90 91 92 ··· 118 다음