곽로그

문제 www.acmicpc.net/problem/15661 15661번: 링크와 스타트 첫째 줄에 N(4 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에 S가 주어진다. 각 줄은 N개의 수로 이루어져 있고, i번 줄의 j번째 수는 Sij 이다. Sii는 항상 0이고, 나머지 Sij는 1보다 크거나 같고, 100 www.acmicpc.net 풀이 스타트와 링크 문제와 달라진 점은 팀을 N/2 N/2로 나누지 않고 각 팀의 수를 다르게 나눠도 된다는 거다. 즉 N=4이라 했을 때 가능한 팀원 수(스타트팀, 링크팀)는 (1,3) (2,2) (3,1)이다. 따라서 이 문제도 스타트팀을 기준으로 생각하면 된다. 스타트팀에 1명을 뽑았다면, 링크팀은 3명이고 그 멤버는 스타트팀이 아닌 사람이다. 코드 imp..

문제 www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 풀이 우선 스타트 팀인 N/2 명을 뽑는다. 이 문제는 N과 M(2) 문제와 같다. 대신 boolean[] isStartTeam 배열을 선언해서, 스타트팀으로 뽑힌 사람의 번호를 true로 한다. 왜냐하면, 스타트 팀을 뽑으면 링크팀은 자동으로 나머지 사람이 되는데, 이때 스타트팀인지 아닌지를 구분하기 위해서이다. 스타트팀인 N/2명을 구했다면, 스타트팀이 아닌 N/2명을 링크팀으로 한다. 그런 다음 이중 for문을 이용해서 ..

문제 www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 풀이 "오늘부터 N+1일째 되는 날 퇴사를 하기 위해서, 남은 N일 동안 최대한 많은 상담을 하려고 한다."라는 조건을 생각해보면, 백준이가 퇴사를 하기 위해서는 백준이의 상담이 N번째 되는 날 안에 끝나야 한다는 말이된다. 상담을 하는 날을 정한다는 행위가 반복된다. 이 때 상담을 하는 날은, 이전 상담 종료일 이후부터 N번째 날이 된다. 다시말해 상담을 하는 날을 정하려면 이전 상담 종료일을 알아야 한다. 따라서 재귀함수의 매개변수로 "이전 상담 종료일"을 넘긴다. 그러면 재귀함수는 "이전 상담 종료일"을 기준으로 N보다 클 때와 작을 때..

1. 문제 www.acmicpc.net/problem/14503 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어 www.acmicpc.net 2. 이 문제에서 배울 점 - 순서도 그리기! 현재 위치를 청소한다. 현재 위치에서 현재 방향을 기준으로 왼쪽방향부터 차례대로 탐색을 진행한다. a) 왼쪽 방향에 아직 청소하지 않은 공간이 존재한다면, 그 방향으로 회전한 다음 한 칸을 전진하고 1번부터 진행한다. b) 왼쪽 방향에 청소할 공간이 없다면, 그 방향으로 회전하고 2번으로 돌아간다. c) 네 방향 모두 청소가 이미 되어있거나 벽인 경우에..

문제 www.acmicpc.net/problem/15684 15684번: 사다리 조작 사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선 www.acmicpc.net 풀이 문제를 두 부분으로 나눌 수 있다. 사다리를 놓는다 -> i번 세로선의 결과가 i번이 나오는지 확인한다 이다. 먼저 사다리를 놓는 경우를 보자. 사다리는 최소 0개 부터 최대 3개까지 놓을 수 있다. 그 중 조건을 만족하는 최소값을 구하는 거다. 위의 문제는 NM과 K(1)과 비슷하다. 현재까지 뽑은 사다리의 갯수와 최솟값을 비교하는 거다. 만약 현재까지 뽑은 사다리의 갯수가 최솟값이상이면 더이상 ..

문제풀이 "칸을 뽑는다"라는 행위가 반복된다. 이 행위가 언제까지 반복되는지를 보면, 현재까지 뽑은 칸의 갯수(pickCount)가 뽑아야하는 칸의 갯수(K)와 같아질 때까지 반복한다. pickCount와 K가 같으면, 현재까지의 칸의 합과 max 값을 비교하면 된다. 위의 로직을 재귀함수로 짰을 때의 구조는 아래와 같다. public static void pickCell(int pickCount, int sum) { if(pickCount>K) { return; } else if(pickCount ==K) { //최댓값과 현재까지의 합을 비교한다 } else { //칸을 뽑는다 } } 이제 칸을 뽑는 경우를 생각해보자. 현재 호출된 함수에서 뽑을 수 있는 칸을 생각해보자. 재귀함수를 가지치기라고 생각한..

문제분석 1부터 N까지 M개를 뽑는데 중복을 허락하지 않고, 오름차순으로 뽑아야한다. 재귀함수 위의 문장을 "숫자를 뽑는다"를 중심으로 생각해보자. 숫자를 언제까지 뽑아야하나 ? 현재까지 뽑은 숫자의 갯수가 M개 미만이면 숫자를 뽑는다 뽑은 숫자의 갯수가 M개이면? 현재까지 뽑은 숫자를 출력한다 로 나타낼 수 있다. * 슷자를 뽑는다/ 숫자를 출력한다의 기준이 되는 상황을 생각해볼 것 → 현재까지 뽑은 숫자의 갯수 public static void pickNumber(뽑아야하는 숫자의 갯수, 현재까지 뽑은 숫자의 갯수) { if(현재까지 뽑은 숫자의 갯수 = 뽑아야 하는 숫자의 갯수) { 현재까지 뽑은 숫자를 출력한다 } else if(현재까지 뽑은 숫자의 갯수 > 뽑아야 하는 숫자의 갯수) { 유효하지..

실수모음 1. 이상한 while 코드 //N보다 큰 곳에서 N쪽으로 접근 int n = N; while(!canPush(n)) { ++n; } int pushCount = getDigit(n) + (n-N); min = Math.min(min, pushCount); 원래의도 n을 누를 수 없으면 하나씩 증가시킨다. while문을 빠져나오는 경우에는 누를 수 있는 경우라 생각하고 빠져나온 n에 대해서 최소누름횟수를 구함 생각하지 못한 것 1) while종료 조건 2) n이 음수가 되는 경우 2. 0 조건을 빼먹음 public static boolean canPush(int n) { while(n>0) { int temp = n%10; if(broken[temp]) { return false; } n = n..