-해법 앞선 문제였던 별 찍기-8 문제와 동일한 풀이로 해결할 수 있다. 윗부분에 중간까지 포함해 출력하고, 아랫부분은 별도로 출력하는 것이다. //윗 부분 반복 for(int i=1;i

-해법 이번 별 찍기에서의 규칙성은 1번째 줄은 첫 번째 열과 마지막 열에 1개, 두 번째 줄은 2개,.... 이런 식으로 가게 된다. 필자의 경우에는 윗부분과 아랫부분으로 나누어서 생각하였고, 윗부분에 중앙 부분까지 포함이 되어있다. // 윗 부분 반복문 for(int i=0;i

-해법 이 문제의 경우 최하단이 2*n-1개의 별을 찍는다는 것을 알 수 있다. 즉, 각 열의 중앙부터 첫 줄은 중앙 +- 0에 , 두 번째 줄은 중앙+-1에, 세 번째는 중앙+-2에.... 식으로 별을 찍어주면 되는데 주의사항은 문제에서는 언급이 되어있지 않지만, 각 별을 찍을 때 별이 마지막이 되어야 한다. 무슨 이야기냐면, [ *] [ ***] [ *****] [ *******] [*********] 식으로 앞자리는 공백으로 채워줘야 하고 별 이후로는 공백을 찍으면 안 된다. 이것 때문에 많은 분들이 출력 형식 오류처리를 받는 것 같다. 이 부분만 주의해주면 된다. import java.util.*; public class Main { public static void main(String[] ar..

-해법 2차원 배열을 사용하여도 되고, 그냥 출력만 해주어도 된다. 그러나 2차원 배열을 사용하면 메모리의 낭비와 2번 탐색하는 문제점이 있기 때문에 단순히 2중 for문만을 이용해서 해결할 수 있다. import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n=sc.nextInt(); for(int i=n;i>0;i--) { for(int j=0;j

-내 생각 정보처리기사를 준비하면서 많이 봤던 별 찍기 문제였다. 2차원 배열을 구현해도 되지만, 메모리 낭비이므로 그냥 출력하는 방식으로 구현하려 했다. 문제의 특징으로는 예제 출력에서 볼 수 있듯이, 각 행마다 N-행의 값의 개수만큼 별을 찍는다. 예를들어 N이 5일 경우, 첫 번째 행은 0번 부터 시작하여, 5-0번 열을 반복한다. 행이 1일 경우는 5-1인 열을 4번만큼 반복한다... 이런식으로 구현해도 되고 반대로 행을 5부터 시작하여 행은 감소시키고 열은 행까지 반복하는 등 여러가지 구현 방법이 가능하다. import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(..

-내 생각 특정 일수가 주어지고 해당 일자의 요일을 구하는 문제이다. 이런 유형의 문제는 처음 풀어봐서 어떻게 풀어야 할지 감을 잡지 못했는데, 잘 생각해보면 1주일이 지날 때마다 7씩 증가하므로, 1/1이 월요이라면, 8일도 월요일, 15일도 월요일.... 식으로 가게 된다. 그러므로 특정 일자 % 7로 어느 요일에 속하는지 알 수 있게 된다. 그렇다면 특정 월과 일이 총 며칠인지 어떻게 구해야 할지 고민해보았는데, 생각해보면 간단하다. 예를 들어 3월 6일이라고 가정한다면 1월과 2월의 총일수를 6일과 더해주면 된다. 각 월의 총일수는 문제에서 주어지므로 구현이 가능해진다. -해법 import java.util.*; public class Main { static int month_Day[] = {0..

-내 생각 하노이 탑의 경우 개념은 알겠는데, 재귀 호출의 늪에 빠져버려서 도저히 머릿속으로 상상이 어렵다.. 그래서 그냥 공식처럼 외우기로 했다.. -해법 하노이 탑을 해결하기 위해서 1번 타워에서 3번 타워로 옮기는 것이 기본으로 수행 알고리즘은, n-1개의 원판을 1->3->2 순으로 타워 롤 옮기고, 2->1->3 순으로 3번에 다시 쌓으면 된다고 한다. 그렇기 때문에 재귀 호출을 통해 인자만 변경하면서 전달해주면 된다. import java.util.*; public class Main { static int n,cnt=0; static StringBuilder sb = new StringBuilder(); static void hanoi(int n,int from,int by,int to) {..

-내 생각 이 문제를 풀다가 약간 소름이 돋았다. 이전에 비슷한 문제를 풀었었던 것 같은데(블로그에 글은 올리지 않았다.) 그 당시에는 이러한 문제를 풀 때 2번부터 기준으로 할 때 1번이 가지는 값은 2번이 가지는 값보다 작은 경우만 카운트해서 풀었던 것 같은데, 그것이 LIS를 학습하고 나서 LIS인 줄 알 수 있었다.. 최대한 LIS로 풀어보기 위해 글을 검색해 보았는데 정확한 풀이법을 알 수 있었다. -해법 우선 A 또는 B 전봇대를 기준으로 오름차순 정렬을 수행한다. 이후 i번을 기준으로 i번 보다 작은 경우 값이 i번 보다 작게 가져야 한다. 즉 전깃줄을 제거하는 것이 아닌, 설치하는 개념으로 생각해보면, 2-2 일 때 1-8이므로 2

-내 생각 이전 글에서 작성했던 가장 긴 증가하는 부분 수열 문제와 동일한 문제라고 생각했다. 원래 이 문제는 단계별 풀어보기 동적 계획법 1에 존재하지 않는 문제인데, 풀게 된 계기는 11054번 문제인 가장 긴 바이 토닉 부분 수열 문제를 해결하기 위해서 먼저 풀어보면 좋다고 하여 풀어보게 되었다. -해법 이 문제는 가장 긴 증가하는 부분 수열 문제와 알고리즘은 완전히 동일하며 반복문 부분만 수정해주면 된다. 즉 시작 인덱스를 1이 아닌, n부터 시작하면 되는 것이다. 자세한 것은 코드를 보자. import java.util.*; public class Main { static int n; static int dp[], cost[]; public static void main(String[] args..

-내 생각 문제 이름은 쉬운 계단 수있은데 쉽지가 않다 ㅋㅋㅋㅋㅋㅋ 당연히 못 풀었고 다른 분들의 글을 참고했다. -해법 이 문제의 경우 dp[N][10]의 2차원 배열을 사용해야 한다. N은 숫자의 자릿수를 의미하며 10은 0~9의 끝자리를 의미한다. 다른 분들의 경우 0~9를 끝자리로 두지 않고 푼 경우도 봤는데, 끝자리로 두고 푼 분들이 더 많았다. 우선 초기 dp배열은 N이 1일 경우이다. 0~9까지 이지만, 0으로 시작하는 경우는 존재하지 않는다고 언급했기 때문에 0을 제외한 1~9는 1자리 수이므로 모두 1로 채워준다. (값들은 각 숫자가 끝자리에 오는 경우의 수를 의미한다.) 이후 N이 2일 경우, 0이 끝자리에 오는 경우는 앞자리가 될 수 있는 수들은 0 -1 , 0 +1이 된다. 그러나 ..