본문 바로가기

Constructive4

[자바] 백준 2873 - 롤러코스터 (java) 문제 : boj2873 필요 알고리즘 개념 구성적, 그리디 정규화된 방식 없이 이 문제만을 위한 규칙이 필요한 구성적 문제이다. 또한 그리디를 적용해 해당 규칙을 정할 수 있긴하다(?). 구현 보통 플래급에서 '구현'이 태그로 있다는건 구현이 엄청 어렵다는 뜻이다 ㅋㅋ ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 사실 규칙자체는 여러 케이스에 대해 마구 그려보면서 머리로 생각해보면 어렵지 않게 규칙을 찾을 수 있다. 문제는.. 2022. 9. 17.
백준 2041 자바 - 숫자채우기 (boj 2041 java) 문제 : boj2041 배열이랑 반복문만 알면 풀 수 있는 순수 아이디어 문제인데도 다이아 티어를 받은 무서운 문제이다. 별다른 알고리즘적 지식이 필요하지 않으므로 풀기 전에 이 글을 보면 얻어갈 수 있는건 아이디어 뿐이다. 따라서 밑으로 내려 풀이를 보자마자 스포가 되므로, 최대한 스스로 풀어보고 풀이를 보는걸 추천한다(하지만 스스로 풀어봤다면 더이상 풀이가 필요없지) 백준1187번을 같이 풀었던 선배같은 후배와 같이 풀었다. 1187때는 결국 난 못풀었고 후배의 도움으로 풀 수 있었지만 이번엔 내가 먼저 풀이를 찾았다. 기분 좋다. ----- 풀이 스포주의 ----- 내 경우엔 여러 방식으로 해보다가, 결국 해답을 찾은 키 아이디어는 배열에 어떤 수가 들어갈지 고민하기 보다, 차이를 어떻게 배치할지 .. 2022. 4. 7.
백준 1187 자바, C++ - 숫자 놀이 (boj 1187 java c++) 문제 : boj1187 감을 제대로 못잡고 있었는데, '수학귀신' 책을 추천해줬던 수학 잘하는 선배같은 동생의 도움으로 풀 수 있었다. 1. 귀납법(귀납 추론)으로 풀 수 있는 문제이다. 1.1 k=1 k를 1부터 증가시켜 나가면서 생각해보자. 우선 k=1일 때, N은 2가 된다. 이 때 2*2-1 = 3개 중 합이 2로 나누어 떨어지는 2개를 뽑는 문제가 된다. 그럼 2*2-1개의 수가 어떻게 나와야 2로 나눌 수 있는 2개를 뽑을 수 있을까? 이 때 모든 경우를 나타내보면 다음과 같다. A. 3개의 수가 모두 짝수일 경우 -> 아무거나 2개 뽑으면 된다. B. 3개의 수가 모두 홀수일 경우 -> 아무거나 2개 뽑으면 된다. C. 3개의 수가 짝수2개, 홀수1개인 경우 -> 짝수 2개를 뽑으면 된다. .. 2022. 4. 1.
백준 2759 자바 - 팬케이크 뒤집기 (BOJ 2759 JAVA) https://www.acmicpc.net/problem/2759 알고리즘 분류를 굳이 따지자면 constructive, ad-hoc, greedy 쪽일 것 같음. 애초에 답으로 가능한 경우 어떤 것이든 출력하면 되기도 하고, 이런 류의 문제를 풀기위한 well-known 스러운 풀이도 없다고 판단되므로 논리적 추론을 통해 이 문제만의 풀이과정을 만들어야 하는 종류의 문제이다. Brute force로 모든 경우를 보면 최대 O(30^30) 이라는 괴랄한 수가 나오므로 절대 무리.. 전 일단 가장 큰 수 부터 차례대로 맨 아래로 가야한다는 부분에 포인트를 맞추고, 그럼 위에서 k개를 뒤집는 방식으로 어떻게 가장 큰 수부터 차례대로 맨 아래로 내릴지 생각해봤다. 결론적으로 제 풀이는 다음과 같음. 가장 큰 .. 2021. 10. 7.