코딩공작소

https://www.acmicpc.net/problem/1074 1074번: Z 한수는 2차원 배열 (항상 2^N * 2^N 크기이다)을 Z모양으로 탐색하려고 한다. 예를 들어, 2*2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. 만약, 2차원 배열의 크기가 2^N * 2^N라서 왼쪽 위에 있는 칸이 하나가 아니라면, 배열을 4등분 한 후에 (크기가 같은 2^(N-1)로) 재귀적으로 순서대로 방문한다. 다음 예는 2^2 * 2^2 크기의 배열을 방문한 순서이다. N이 주어졌을 때, (r, www.acmicpc.net 어떤 천재의 풀이를 이해만 했다... 재귀를 써야하나 여러가지 방법을 생각했지만 2^15까지의 배열의 크기가 나오는 문제이다. 분할정복이란 가..

https://www.acmicpc.net/problem/1018 1018번: 체스판 다시 칠하기 첫째 줄에 N과 M이 주어진다. M과 N은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개 줄에는 체스판의 색 상태가 주어진다. B는 검정색이며, W는 흰색이다. www.acmicpc.net 흠.. 간만에 적응 안되는 쉬운문제였다. 시뮬?? 그리디?? 그냥 세우면 됐다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061#include using namespace std; /*1.8x8의 격자판을 만들어야한다. 2.8x8을 완전 탐색..

https://www.acmicpc.net/problem/17136 17136번: 색종이 붙이기 과 같이 정사각형 모양을 한 다섯 종류의 색종이가 있다. 색종이의 크기는 1×1, 2×2, 3×3, 4×4, 5×5로 총 다섯 종류가 있으며, 각 종류의 색종이는 5개씩 가지고 있다. 색종이를 크기가 10×10인 종이 위에 붙이려고 한다. 종이는 1×1 크기의 칸으로 나누어져 있으며, 각각의 칸에는 0 또는 1이 적혀 있다. 1이 적힌 칸은 모두 색종이로 덮여져야 한다. 색종이를 붙일 때는 종이의 경계 밖으로 나가서는 안되고, 겹쳐 www.acmicpc.net 1.큰 종이부터 붙이면 되나보다 해서 큰종이 부터 붙였음. 2.반례가 있어서 작은종이로 오히려 더 작은 케이스를 만드는 경우가 있어서 5~1까지 종이의..

https://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 첫번째 풀었을때는, 다른 코드를 보고 공부해서 풀었다. 두번째 풀었을 때는 15분 컷으로 풀었다... 뿌듯 먼저 들었던 생각은, 두개의 팀을 나눠야 한다는 것이었고 조합을 이용해야겠다 생각해서 dfs재귀를 이용하였다. 두팀이기 때문에 단순히 true/false로 나누어 주면 된다고 생각했고, true를 재귀를 통해 새겨준 후, 길이의 반이 되면 팀원끼리의 능력치를 더해주었다. 1 2 3 4 5 6 7 8 9 10 11..

https://www.acmicpc.net/problem/15683 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감시할 수 있는 방법은 다음과 같다. 1번 CCTV는 한 쪽 방향만 감시할 수 있다. 2번과 3번은 두 방향을 감시할 수 있는데, 2번은 감시하는 방향이 서로 반대방향이어야 하고, 3번은 직각 방향이어야 한다. 4번은 세 방향, 5번은 네 방향을 감시할 www.acmicpc.net 처음 볼때는 아예 접근방법도 모르고 너무 복잡하다고 생각했었다.. 근데 막상 좀 제대로 풀고나니까 1시간정도 걸렸었다. 가장 중요한 것은 ..

각 자릿수들을 만져서 30의 배수를 찾는 문제인데 문자열을 다루는 것은 파이썬이 편하기 때문에 파이썬으로 해주었다. 30의 배수가 되기 위한 특성을 먼저 고려해주었다. 그리고 나니까 풀렸다... 문제 어느 날, 미르코는 우연히 길거리에서 양수 N을 보았다. 미르코는 30이란 수를 존경하기 때문에, 그는 길거리에서 찾은 수에 포함된 숫자들을 섞어 30의 배수가 되는 가장 큰 수를 만들고 싶어한다. 미르코를 도와 그가 만들고 싶어하는 수를 계산하는 프로그램을 작성하라. 입력 N을 입력받는다. N는 최대 105개의 숫자로 구성되어 있으며, 0으로 시작하지 않는다. 출력 미르코가 만들고 싶어하는 수가 존재한다면 그 수를 출력하라. 그 수가 존재하지 않는다면, -1을 출력하라. 1 2 3 4 5 6 7 8 9 1..

문제를 잘 이해하면 쉬운 그리디 문제였다. 정렬을 하겠다는 생각과 가장 작은것에 K를 곱하면 되는것이 키포인트였다. 문제 N(1≤N≤100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다. 하지만 여러 개의 로프를 병렬로 연결하면 각각의 로프에 걸리는 중량을 나눌 수 있다. k개의 로프를 사용하여 중량이 w인 물체를 들어올릴 때, 각각의 로프에는 모두 고르게 w/k 만큼의 중량이 걸리게 된다. 각 로프들에 대한 정보가 주어졌을 때, 이 로프들을 이용하여 들어올릴 수 있는 물체의 최대 중량을 구해내는 프로그램을 작성하시오. 모든 로프를 사용해야 할 필요는 없으며, 임의로 몇 개..

가장 기본적인 그리디 알고리즘인거 같다.. 유사한 문제가 많고 가장 큰거에서 부터 시작해서 빼주면서 sum을 구해주면 됨. 문제 타로는 자주 JOI잡화점에서 물건을 산다. JOI잡화점에는 잔돈으로 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 충분히 있고, 언제나 거스름돈 개수가 가장 적게 잔돈을 준다. 타로가 JOI잡화점에서 물건을 사고 카운터에서 1000엔 지폐를 한장 냈을 때, 받을 잔돈에 포함된 잔돈의 개수를 구하는 프로그램을 작성하시오. 예를 들어 입력된 예1의 경우에는 아래 그림에서 처럼 4개를 출력해야 한다. 입력 입력은 한줄로 이루어져있고, 타로가 지불할 돈(1 이상 1000미만의 정수) 1개가 쓰여져있다. 출력 제출할 출력 파일은 1행으로만 되어 있다. 잔돈에 포함된 매수를 출력하..

보호되어 있는 글입니다.

그리디 라는 테마가 있기때문에 그리디 라는 생각을 먼저했었다. 총액에서 동전들을 전부 사용해가면서 구해봐야 하기 때문에 어차피 그리디로 돌려야 할것이라고 생각했을것 같다. 먼저 떠오른 생각은, 최소한의 동전을 사용해야하기 때문에 가장 큰 금액부터 사용해야된다는 것이었고, 사용할 수 있는 가장 큰 동전을 구해준 것이다. 그 후, 차차 아래의 동전들도 사용해가면서 개수를 구해주어야 겠다고 생각했다.(while문 부분이 키 포인트였다.) 문제 준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다. 동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1..