김머성 블로그

[BAE/<JOON> 문제풀이] 1114. 통나무 자르기

https://www.acmicpc.net/problem/1114 1114번: 통나무 자르기 첫째 줄에 두 개의 수를 출력한다. 첫 번째 수는 가장 긴 조각의 길이이고, 두 번째 수는 그 때 처음 자르는 위치를 출력한다. 만약 가능한 것이 여러 가지라면, 처음 자르는 위치가 작은 것을 출 www.acmicpc.net 서론 파라메트릭 그냥 f, r 외워야할 것 같다. 파라메트릭 풀 때마다 원숭이마냥 이거 브루트포스하고 있는게 너무 한심하다. 첫 자르는 위치도 진짜 쉬운데 못 떠올려서 시간 너무 많이 날림. 근데 풀 때는 조각 길이 로직만 의심하고 첫 자르는 위치는 의심을 못했다. 풀이 1. 파라메트릭으로 가장 짧은 긴 조각 길이 구하기 현재 mid 값이 될 때까지 조각 길이를 더하다가 넘거나 같아질 때마다..

[BAE/<JOON> 문제풀이] 4781. 사탕 가게

https://www.acmicpc.net/problem/4781 4781번: 사탕 가게 각 테스트 케이스의 첫째 줄에는 가게에 있는 사탕 종류의 수 n과 상근이가 가지고 있는 돈의 양 m이 주어진다. (1 ≤ n ≤ 5,000, 0.01 ≤ m ≤ 100.00) m은 항상 소수점 둘째자리까지 주어진다. 다음 n개 www.acmicpc.net 서론 아무리봐도 코드가 맞는데 틀려서 검색해보니 컴퓨터가 실수를 다루는 방식을 몰랐었다. 풀이 그냥 배낭 문제다. 그런데 특이하게도 가격이 실수다. 소수부분 길이는 2로 고정되어있기 때문에 100을 곱하기만 하면 정수로 바꿀 수 있을 거라 생각했다. 하지만 내가 회사 프로젝트를 하면서도 가끔 봤던 현상인데 실수를 처음 초기화 할때는 값에 문제가 없다가도 몇번 연산을..

[BAE/<JOON> 문제풀이] 17090. 미로 탈출하기

https://www.acmicpc.net/problem/17090 17090번: 미로 탈출하기 크기가 N×M인 미로가 있고, 미로는 크기가 1×1인 칸으로 나누어져 있다. 미로의 각 칸에는 문자가 하나 적혀있는데, 적혀있는 문자에 따라서 다른 칸으로 이동할 수 있다. 어떤 칸(r, c)에 적힌 문 www.acmicpc.net 서론 그래프 문제 = 티어 -3 난이도 = 실버 1문제 아이디어 직관도 쉽고 풀이도 쉽다. 아이디어 출발지를 미로안으로 설정해서 BFS를 하면 TLE가 날 것 같아서 경로를 역으로 설정하고 미로 외부에서 시작해서 노드 방문 여부를 체크하며 탐색했다. 풀이 아이디어가 전부라 진짜 쓸게 없다. 주말이니까 날먹해야지 코드 더보기 #include #include #include #incl..

[BAE/<JOON> 문제풀이] 17179. 케이크 자르기

https://www.acmicpc.net/problem/17179 17179번: 케이크 자르기 첫 번째 줄에 자르는 횟수가 담긴 목록의 길이 N과 자를 수 있는 지점의 개수 M, 그리고 롤 케이크의 길이인 정수 L이 주어진다. (1 ≤ N ≤ M ≤ 1,000, 1 < L ≤ 4,000,000) 다음 M줄에 걸쳐 자를 수 있는 www.acmicpc.net 서론 무슨 문젠지 모르겠어서 태그 봤는데 파라메트릭이 또,, 앞으로 문제가 DP 같은데 입력값이 좀 이상하다 싶으면 파라메트릭으로 가야겠다. 이건 판정 방법을 모르겠음. 문제를 많이 안풀어서 그런가. 내일은 통나무 풀어봐야겠다. 이 문제 보니까 그건 이중 파라메트릭 같음. 아이디어 케익을 자르는 구간 고민하지 말고 다 잘라놓은 다음에 합치기 합치면서 ..

[BAE/<JOON> 문제풀이] 1563. 개근상

https://www.acmicpc.net/problem/1563 1563번: 개근상 백준중학교에서는 학기가 끝날 무렵에 출결사항을 보고 개근상을 줄 것인지 말 것인지 결정한다. 이 학교는 이상해서 학생들이 학교를 너무 자주 빠지기 때문에, 개근상을 주는 조건이 조금 독 www.acmicpc.net 서론 내가 복잡하게 푼건진 모르겠는데 DP 축이 많아서 점화식 세울 때 헷갈린다. 아이디어 솔직히 아이디어랄건 없고 그냥 문제에서 주어진 점화식을 구현하면 된다. 지금 연속 결석 횟수 몇번인지, 지각 여부 ( 지각 기회는 딱 1번 뿐임 ), 현재 몇 번째 출결인지 3가지 요소로 계산 가능 풀이 진짜 순수 DP 라서 점화식밖에 쓸게 없다. :D DP[i][j][k] = i 번째날에 j번 지각하고 현재 k번 연속..

[BAE/<JOON> 문제풀이] 1695. 펠린드롬 만들기

https://www.acmicpc.net/problem/1695 1695번: 팰린드롬 만들기 앞에서 뒤로 보나, 뒤에서 앞으로 보나 같은 수열을 팰린드롬 이라고 한다. 예를 들어 {1}, {1, 2, 1}, {1, 2, 2, 1}과 같은 수열은 팰린드롬 이지만, {1, 2, 3}, {1, 2, 3, 2} 등은 팰린드롬이 아니다. 한 수열 www.acmicpc.net 서론 어제까지 골4였는데 오늘보니까 골3 되어있음. 신기하다. 아이디어 사실 웰논 알고리즘만 알면 아이디어는 떠올리기 매우 쉽다. LCS ( Longest Common String ) 라고 정말 옛날에 배운 알고리즘이다. 말 그대로 두 문자열에서 가장 긴 공통 문자열을 찾아내는 알고리즘이다. 팰린드롬이 되기 위해 필요한 추가 문자 갯수는 당..