D36CHOI

from sys import stdin n,m = map(int, stdin.readline().split()) parent = [0]*(n+1) def find_parent(a): if a != parent[a]: parent[a] = find_parent(parent[a]) return parent[a] def union_parent(a,b): pa = find_parent(a) pb = find_parent(b) if pa > pb: parent[a] = b else: parent[b] = a for i in range(1,n+1): parent[i] = i for i in range(n): li = list(map(int,stdin.readline().split())) for j in range(..

문제 https://www.acmicpc.net/problem/14503 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어 www.acmicpc.net 분류 구현과 시뮬레이션 아이디어 설명대로 구현하되, DFS 모델에서 백트래킹이 없다고 보면된다. 다음 경우의 수를 찾으면 바로 break 걸어서 다른 경우의 수를 큐에 추가하지 않도록 해야한다. 문제를 꼼꼼히 읽지 않아 후진의 경우 를 코드로 구현하지않아서 이거 왜안돼?? 만 외친 채 40분정도를 날린 기분이다. 구현문제는 기본적으로 문제를 자아아알 읽는것이 정답의 길이다. 방향전환과 진행..

StringTokenizer 문자열이 특정 구분자 (이를 delimeter라 한다)로 연결 되어있으면 2가지 방법으로 문자열을 쪼갠다. 1. String.split() 2. java.util.StringTokenizer 1과 2의 차이는 1은 정규표현식(regular expression), 2는 문자로 구분을 한다는 것이다. String.split() class Main { public static void main(String\[\] args) { String str = "안녕하세요,만나서-반가워요"; String\[\] tokens = str.split(",|-"); for (String token : tokens) { System.out.println(token); } } } StringTokeni..

문제 www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변� www.acmicpc.net 테마 브루트포스 아이디어 테트로미노들은 기본모양에서 90도씩 회전, x/y축 반전(뒤집기) 등이 가능하다. 네모의 칸수는 총 4칸. 돌리고 뒤집고 돌리고 뒤집고 ... [[0,0,0], [0,0,0], [0,0,0]] 3*3 이내의 좌표로 모든 테트로미노의 좌표가 표현 가능하다. 무식하지만 총 19개의 테트로미노 경우의 수를 'tetrominos' 배열에 저장해 활용했다. N*M 배열에서 각 i행j열 좌..

문제 www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 분류 다이나믹 프로그래밍 아이디어 날짜를 index로 삼아 (1일째 = dp[1]...) 해당 일까지 얻을 수 있는 금액의 최대 이윤을 저장한다. bottom-up 방식으로, 최대 이윤을 구할 수 있는 N일부터 dp[i] 를 계산한다. 점화식은 dp[i] = max(dp[i]+dp[time[i]+i] , max_pay) 다. max_pay 는 해당일까지 계산한 최대이윤 값이다. 만약 N=7 기준으로, 7일차에 일할 경우 받는 pay = 50, 걸리는 시간 = 1이면 dp[7] = 50 이다. max_pay 또한 0에서 50 이 된다. 6일차에..