본문 바로가기

BOJ

 (4)
[백준] 12865번 평범한 배낭 문제 제목처럼 평범한 Knapsack 문제 입니다. 하지만, 너무 간만에 봐서 다 까먹고 쉽게 풀지 못한 문제이기도 합니다...ㅠㅠ backtracking으로 풀어도 봤습니다. dfs로 재귀방식으로 모든 경우를 따져봤지만 역시나 시간초과가 뜹니다. 결국 DP로 풀어야 하는 문제입니다! DP 변수의 각 index(물건) 마다 0~k까지의 무게에 대해 최대값을 넣어주면 됩니다. 2가지 경우로 나눠서 풀어주기만 하면 간단합니다. 1) i 번째 물건을 안넣는 경우 2) i 번째 물건을 넣는 경우 1번의 경우는 그냥 i-1의 무게를 유지해주면 되는 문제고, 2번의 경우는 현재 무게( j ) - 넣고자 하는 물건의 무게에 해당하는 v값을 더해주면 됩니다. 대신 넣을 때는 주의해야 할것이, 넣는 것이 오히려 안넣을 ..
[백준] 9251번 LCS 단순히 LIS(Longest Increasing Subsequence) 처럼 풀려고 하다가 엄청 헤멘 문제 입니다.. LCS를 해결하는 방식이 있습니다. 우선 표를 통해서 먼저 설명하겠습니다. (문제에서 주어진 것 처럼 ACAYKP, CAPCAK를 활용합니다) A C A Y K P 0 0 0 0 0 0 0 C 0 0 1 1 1 1 1 A 0 1 1 2 2 2 2 P 0 1 1 2 2 2 3 C 0 1 2 2 2 2 3 A 0 1 2 3 3 3 3 K 0 1 2 3 3 4 4 최종적인 표의 모습입니다. 알면 쉽게 풀리는.. 2가지 규칙만 적용하면 끝나는 문제입니다. 1) 같은 문자가 나오면 대각 왼쪽 상단 + 1 2) 다른 문자가 나오면 max(상, 좌) 먼저, 각 문자 배열 + 1만큼 DP(Dynamic..
[백준] 2206번 벽 부수고 이동하기 벽 부수는 것을 처음에 너무 간단하게만 생각했다가 여러번 틀린 문제입니다. queue에 넣는 조건을 잘 나누지 않으면 메모리 초과가 나오기 십상이니 명확하게 구분해야만 해결할 수 있는 문제였습니다. 먼저, 현재 좌표의 방문 여부를 벽을 부순적이 있는 경우와 없는 경우로 나눠서 진행해야 합니다. 안그러면 아래 예시와 같은 경우에 -1이 나오게 됩니다. 4 4 0000 0 1 1 1 00 1 1 00 10 한번 방문해서 실패했다고 무조건 visited를 true로 바꿔주면..! 아래처럼 되버려서 실패하고 맙니다. (0,0)->(0,1)->(1,1)->(2,1)->(3,1) 경로로 이동해서 한번 실패했다면, 해당 경로는 전부 visited = true가 되버립니다. 그러면, (0,0)->(1,0)->(2,0)..
[백준] 13460번 구슬 탈출 2 [풀이] 고려해야될 케이스가 많아서 생각보다 애를 먹었던 문제입니다.. ㅠ 우선 제가 풀이한 방식은 다음과 같습니다. 1. 각 지점별로 사방으로 이동을 합니다. 2. 빨강, 파랑 둘다 '#'를 만나거나 서로 겹치게 되면 멈추고 그 자리를 기억합니다. 만약 그 중 'O'가 있다면 가능한지 불가능한지 구분해줍니다. 가능하다면 바로 그 횟수를 출력하면 되고, 불가능하다면 그 위치에서는 더이상 이동 하지 않습니다. 여기에서 주의해야 할 부분은 visited를 빨강과 파랑 둘다 기록해줘야 한다는 것입니다. 처음에는 어짜피 빨간색만 구멍에 들어가면 되니까 빨간공만 기록해주면 되지 않을까 하였지만, 빨간색은 같은 위치인데 파란색의 위치가 달라 결과가 달라지는 경우가 생기더군요.. ! 어떻게 보면 BFS로 간단히 풀 ..

티스토리툴바